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

Kaltofen, Erich

doi:10.1090/S0025-5718-1995-1270621-1

Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems
HTML articles powered by AMS MathViewer

by Erich Kaltofen PDF

Math. Comp. 64 (1995), 777-806 Request permission

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

Robert R. Bitmead and Brian D. O. Anderson, Asymptotically fast solution of Toeplitz and related systems of linear equations, Linear Algebra Appl. 34 (1980), 103–116. MR 591427, DOI 10.1016/0024-3795(80)90161-5
Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), no. 3, 259–295. MR 604867, DOI 10.1016/0196-6774(80)90013-9
David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
Don Coppersmith, Solving homogeneous linear equations over $\textrm {GF}(2)$ via block Wiedemann algorithm, Math. Comp. 62 (1994), no. 205, 333–350. MR 1192970, DOI 10.1090/S0025-5718-1994-1192970-7
Philippe Delsarte, Yves V. Genin, and Yves G. Kamp, A generalization of the Levinson algorithm for Hermitian Toeplitz matrices with any rank profile, IEEE Trans. Acoust. Speech Signal Process. 33 (1985), no. 4, 964–971. MR 809473, DOI 10.1109/TASSP.1985.1164645

A probabilistic remark on algebraic program testing

7

Process scheduling in DSC and the large sparse linear systems challenge

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, DOI 10.1016/0024-3795(86)90279-X
Thomas Kailath, Sun Yuan Kung, and Martin Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), no. 2, 395–407. MR 533501, DOI 10.1016/0022-247X(79)90124-0
Erich Kaltofen, Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Applied algebra, algebraic algorithms and error-correcting codes (San Juan, PR, 1993) Lecture Notes in Comput. Sci., vol. 673, Springer, Berlin, 1993, pp. 195–212. MR 1251979, DOI 10.1007/3-540-56686-4_{4}4

Factoring high-degree polynomials by the black box Berlekamp algorithm

Processor-efficient parallel solution of linear systems

The positive characteristic and singular cases

Erich Kaltofen and B. David Saunders, On Wiedemann’s method of solving sparse linear systems, Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991) Lecture Notes in Comput. Sci., vol. 539, Springer, Berlin, 1991, pp. 29–38. MR 1229306, DOI 10.1007/3-540-54522-0_{9}3

Solving large sparse linear systems over finite fields

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), no. 203, 319–349. MR 1182953, DOI 10.1090/S0025-5718-1993-1182953-4
James L. Massey, Shift-register synthesis and $\textrm {BCH}$ decoding, IEEE Trans. Inform. Theory IT-15 (1969), 122–127. MR 242556, DOI 10.1109/tit.1969.1054260
Michael T. McClellan, The exact solution of systems of linear equations with polynomial coefficients, J. Assoc. Comput. Mach. 20 (1973), 563–588. MR 347068, DOI 10.1145/321784.321787
Robert T. Moenck and John H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 65–73. MR 575681

Doubling algorithms for Toeplitz and related equations

Victor Pan, Parametrization of Newton’s iteration for computations with structured matrices and applications, Comput. Math. Appl. 24 (1992), no. 3, 61–75. MR 1166478, DOI 10.1016/0898-1221(92)90215-4
Carl Pomerance and J. W. Smith, Reduction of huge, sparse matrices over finite fields via created catastrophes, Experiment. Math. 1 (1992), no. 2, 89–94. MR 1203868, DOI 10.1080/10586458.1992.10504250

A separator-based framework for automated partitioning and mapping of parallel algorithms for numerical solution of PDEs

J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225
Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137
Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 216–226. MR 575692

Effective polynomial computations