Journal of the ACM · 1978 · 258 citations · 5 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingMatrix ComputationParallel Algorithm DesignParallel ArchitecturesParallel Numerical Linear AlgebraParallel Numerical MethodsLinear System SolversParallel Linear SolversParallel Linear System SolversParallel Matrix AlgorithmsParallel Matrix InversionParallel Solvers
In this paper three stable parallel algorithms for solving dense and tndlagonai systems of lmear equations are discussed The algorithms are based on Givens' reduction of a matrix to the upper triangular form The algorithm for the dense case requires O(n) time steps compared to O(n log n) steps for Gausslan ehmmatlon with pivoting (in the absence of certain features of machine logic and hardware) For the trldlagonal case, one of the algorithms presented here is superior to the best previous algorithm in that with a modest increase in time It does not fall if any of the leading pnnclpal submatrlces is singular, the probablhty of over-or underflow is minimized, and the error bound does not grow exponentially Furthermore, it is most statable when only a hmtted number of processors ts available.
5
The Algebraic Eigenvalue Problem
E. I., J. H. Wilkinson · Mathematics of Computation · 1966 · 5.2K citations
Fast Parallel Matrix Inversion Algorithms
L. Csanky · SIAM Journal on Computing · 1976 · 403 citations