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 R. A. DeMillo and R. J. Lipton, A probabilistic remark on algebraic program testing, Inform. Process. Lett. 7 (1978), 193-195. 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 anonymous@ftp.cs.rpi.edu in directory kaltofen)
- 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 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 anonymous@ftp.cs.rpi.edu in directory kaltofen) 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.
- 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 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.
- 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 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.
- 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 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.
- 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, Kluwer, Boston, MA, 1993.
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Math. Comp. 64 (1995), 777-806
- MSC: Primary 65F50; Secondary 15A06, 65Y05
- DOI: https://doi.org/10.1090/S0025-5718-1995-1270621-1
- MathSciNet review: 1270621