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?)

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