Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems

Author: Erich Kaltofen
Journal: Math. Comp. 64 (1995), 777-806
MSC: Primary 65F50; Secondary 15A06, 65Y05
MathSciNet review: 1270621
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: By using projections by a block of vectors in place of a single vector it is possible to parallelize the outer loop of iterative methods for solving sparse linear systems. We analyze such a scheme proposed by Coppersmith for Wiedemann's coordinate recurrence algorithm, which is based in part on the Krylov subspace approach. We prove that by use of certain randomizations on the input system the parallel speed up is roughly by the number of vectors in the blocks when using as many processors. Our analysis is valid for fields of entries that have sufficiently large cardinality. Our analysis also deals with an arising subproblem of solving a singular block Toeplitz system by use of the theory of Toeplitz-like matrices.

References [Enhancements On Off] (What's this?)

  • [1] R. R. Bitmead and B. D. O. Anderson, Asymptotically fast solution of Toeplitz and related systems of linear equations, Linear Algebra Appl. 34 (1980), 103-116. MR 591427 (81m:65044)
  • [2] R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), 259-295. MR 604867 (82d:65033)
  • [3] D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), 693-701. (Available from in directory kaltofen) MR 1129288 (92i:68068)
  • [4] D. Coppersmith, Solving homogeneous linear equations over $ GF(2)$ via block Wiedemann algorithm, Math. Comp. 62 (1994), 333-350. MR 1192970 (94c:11124)
  • [5] P. Delsarte, Y. V. Genin, and Y. G. Kamp, A generalization of the Levinson algorithm for Hermitian Toeplitz matrices with any rank profile, IEEE Trans. Acoust. Speech Signal Process. 33 (1985), 964-971. MR 809473 (87h:65052)
  • [6] R. A. DeMillo and R. J. Lipton, A probabilistic remark on algebraic program testing, Inform. Process. Lett. 7 (1978), 193-195.
  • [7] A. Diaz, M. Hitz, E. Kaltofen, A. Lobo, and T. Valente, Process scheduling in DSC and the large sparse linear systems challenge, Proc. DISCO '93 (A. Miola, ed.), Lecture Notes in Comput. Sci., vol. 722, Springer-Verlag, Berlin and New York, 1993, pp. 66-80. (Available from in directory kaltofen)
  • [8] I. Gohberg, T. Kailath, and I. Koltracht, Efficient solution of linear systems of equations with recursive structure, Linear Algebra Appl. 80 (1986), 81-113. MR 851934 (87i:65058)
  • [9] T. Kailath, S.-Y. Kung, and M. Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), 395-407. MR 533501 (80k:65029)
  • [10] E. Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Proc. AAECC-10, Lecture Notes in Comput. Sci., vol. 673 (G. Cohen, T. Mora, and O. Moreno, eds.), Springer-Verlag, Berlin and New York, 1993, pp. 195-212. (Available from in directory kaltofen) MR 1251979 (94k:11134)
  • [11] E. Kaltofen and A. Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, Proc. Internat. Sympos. Symbolic Algebraic Comput. ISSAC '94 (J. von zur Gathen and M. Giesbrecht, eds.), ACM Press, New York, 1994, pp. 90-98. (Available from in directory kaltofen)
  • [12] E. Kaltofen and V. Pan, Processor-efficient parallel solution of linear systems II: The positive characteristic and singular cases, Proc. 33rd Annual Sympos. Foundations of Comput. Sci., 1992, pp. 714-723.
  • [13] E. Kaltofen and B. D. Saunders, On Wiedemann's method for solving sparse linear systems, Proc. AAECC-9, Lecture Notes in Comput. Sci., vol. 539, Springer-Verlag, Berlin and New York, 1991, pp. 29-38. (Available from in directory kaltofen) MR 1229306
  • [14] B. A. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, Advances in Cryptology: CRYPTO '90 (A. J. Menezes and S. Vanstone, eds.), Lecture Notes in Comput. Sci., vol. 537, Springer-Verlag, Berlin and New York, 1991, pp. 109-133.
  • [15] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319-349. MR 1182953 (93k:11116)
  • [16] J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory 15 (1969), 122-127. MR 0242556 (39:3887)
  • [17] M. T. McClellan, The exact solution of systems of linear equations with polynomial coefficients, J. Assoc. Comput. Mach. 20 (1973), 563-588. MR 0347068 (49:11788)
  • [18] R. T. Moenck and J. H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, Proc. EUROSAM '79, Lecture Notes in Comput. Sci., vol. 72, Springer-Verlag, Berlin and New York, 1979, pp. 65-73. MR 575681 (81g:65045)
  • [19] M. Morf, Doubling algorithms for Toeplitz and related equations, Proc. 1980 IEEE Internat. Conf. Acoust. Speech Signal Process., IEEE, Piscataway, NJ, 1980, pp. 954-959.
  • [20] V. Pan, Parameterization of Newton's iteration for computations with structured matrices and applications, Comput. Math. Appl. 24 (1992), 61-75. MR 1166478 (93a:65041)
  • [21] C. Pomerance and J. W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes, Experiment. Math. 1 (1992), 89-94. MR 1203868
  • [22] E. J. Schwabe, G. E. Blelloch, A. Feldmann, O. Ghattas, J. R. Gilbert, G. L. Miller, D. R. O'Hallaron, J. R. Shewchuk, and S.-H. Teng, A separator-based framework for automated partitioning and mapping of parallel algorithms for numerical solution of PDEs, Manuscript, Carnegie Mellon Univ., Pittsburgh, PA, July 1993.
  • [23] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), 701-717. MR 594695 (82m:68078)
  • [24] D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), 54-62. MR 831560 (87g:11166)
  • [25] R. Zippel, Probabilistic algorithms for sparse polynomials, Proc. EUROSAM '79, Lecture Notes in Comput. Sci., vol. 72, Springer-Verlag, Berlin and New York, 1979, pp. 216-226. MR 575692 (81g:68061)
  • [26] -, Effective polynomial computations, Kluwer, Boston, MA, 1993.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F50, 15A06, 65Y05

Retrieve articles in all journals with MSC: 65F50, 15A06, 65Y05

Additional Information

Keywords: Sparse linear systems, parallel and distributed computation, randomized algorithms, finite fields, exact arithmetic, block Toeplitz matrices, Krylov subspaces
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society