- 1.:\llender. E., Beals, R., and Ogihara, M., The complexity of matrix rank and feasible systems of linear equations, in" Proc. 28th STOC (1996), 161-167. Google Scholar
- 2.Borodin, A., 3. yon zur Gathen, and J. Hopcroft, Fast parallel matrix and GCD computations, Inform. and Control 52 (1982), 241-256.Google Scholar
- 3.Csanky, L., Fast. parallel matrix inversion algorithms, SI.4,1I J. Comput. 5 (1976), 618-623.Google Scholar
- 4.Demmel, .J. W., Trading off parallelism and numerical accuracy, Tech. Rep. CS-92-179, Univ. of Tennessee, June 1992 (Lapack Working Note 52). Google Scholar
- 5.Eberly, W., Efficient Parallel Independent Subsets and Matrix Factorizations, in: Proc. 3rd IEEE Symposium on Parallel and Distributed Processing (1991), 204-211.Google Scholar
- 6.Von zur Gathen, J., Parallel Linear Algebra, in: J. Reif, ed., Synthesis of Parallel Algorithm(Morgan and Kaufmatin Publishers, San Mateo, 1993) 573-617.Google Scholar
- 7.(3olllb, G. H. and C. F. Van Loan, Matrix Computations University (Tl,e Johns Hopkins Press, Baltimore, 1989).Google Scholar
- 8.Greenlaw. R. H. J. Hoover, and "W. L. Ruzzo, A Compen<iillm of ProMems Complete for P, Technical Report 91-05-01, Dept. of Colnputer Science and Engineering, University of Washingt.on (1991).Google Scholar
- 9.Anderson. E. et al. Lapack User's Guide, (Society for Industrial and Applied Mathematics, Philadelphia, 1992). Google Scholar
- 10.Leoncini, M., How Much Cem We Speedup Gaussian EliJllinat.ion with Pivoting? in' Proc. 6th A CM ,qymp. on Parallel Algorith.ms and Architectures (1994) 290- 297.lo,r.nal o.{ Computer ond System Science.s, t.o apperil'. Google Scholar
- 11.I,eoncini. M. Manzini. G., and 'Margara, L., Parallel colni#lexity of Householder QR factorization, in: Proc. Eul'opea# Sy11#p. o.n .41gorithm.s (1996), Lecture Notes i1# ("Olnl)uter Science 1136, 290-301. Google Scholar
- 12.Sigmoll, N., Matlab Primer, The MATH WORNS Inc., 199.1.Google Scholar
- 13.Pan. \.'. Colnplexity of Parallel Matrix Computations, Th,orcticol Comp.uter Science 54 (1987), 65-85. Google Scholar
- 14.Reif. 3. H., Depth-first. search is inherently sequential, I,.L l5"oc. Lc-tt. 20 (1985)229-234.Google Scholar
- 15.{Ic'if. 3. H. O(log2 T#) Time Efficient Parallel FactorizatiolJ of Dense. Sparse Separable, and Banded Matrices. in: Proc. 6l.h ACM ,5'ymp. o# Parallel Algo rithms and .4r#hitecturc:.# (1991) 278-- 289. Google Scholar
- 16.San#ell, A. H. and 12).I. Nuck, On Stable Parallel Linear Svs,.elll Solvers, J..4 (?M 25 (1978), 81-91. Google Scholar
- 17.Vavasis, S.A. Gaussian Elimination with Pivoting is P-complete, SI.-IM J. Disc. Math. 2 (1989), 413-423. Google Scholar
Index Terms
- On the parallel complexity of matrix factorization algorithms
Recommendations
Highly Scalable Parallel Algorithms for Sparse Matrix Factorization
In this paper, we describe scalable parallel algorithms for symmetric sparse matrix factorization, analyze their performance and scalability, and present experimental results for up to 1,024 processors on a Cray T3D parallel computer. Through our ...
On sparse matrix reordering for parallel factorization
ICS '94: Proceedings of the 8th international conference on SupercomputingTo minimize the amount of computation and storage for parallel sparse factorization, sparse matrices have to be reordered prior to factorization. We show that none of the popular ordering heuristics proposed before, namely, mulitple minimum degree and ...
Heuristics for exact nonnegative matrix factorization
The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that $$X = WH$$X=...
Comments