Abstract
We present a parallel computational method for the QR decomposition with column pivoting of a sparse matrix by means of Modified Gram-Schmidt orthogonalization. Nonzero elements of the matrix M to be decomposed are stored in a one-dimensional doubly linked list data structure. We discuse a strategy to reduce fill-in in order to get memory savings and decrease the computation times. As an application of QR decomposition, we describe the least squares problem. This algorithm was designed for a message passing multiprocessor and has been evaluated on a Cray T3D, using the Harwell-Boeing sparse matrix collection.
This work was supported by the Spanish CICYT under contract TIC92-0942-C03 and by the TRACS Programme under the Human Capital and Mobility Programme of the European Union (grant number ERB-CHGE-CT92-0005)
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Golub, G.H., Van Loan, C.F.: Matrix Computations. The Johns Hopkins University Press, second edition (1989)
Bischof, C.H.: Adaptive Blocking in the QR Factorization. The Journal of Supercomputing, 3 (1989) 193–208
Zapata, E.L., Lamas, J.A., Rivera, F.F., Plata, O.G.: Modified Gram-Schmidt QR Factorization on Hypercube SIMD Computers. Journal of Parallel and Distributed Computing, 12 (1991) 60–69
Waring, L.C., Clint, M.: Parallel Gram-Schmidt Orthogonalisation on a Network of Transputers. Parallel Computing, 17 (1991) 1043–1050
Hendrickson, B.: Parallel QR Factorization Using the Torus-Wrap Mapping. Parallel Computing, 19 (1993) 1259–1271
Bendtsen, C., Hansen, P.C., Madsen, K., Nielsen, H.B., Pinar, M.: Implementation of QR Up and Downdating on a Massively Parallel Computer. Parallel Computing, 21 (1995) 49–61
Kratzer, S.G.: Sparse QR Factorization on a Massively Parallel Computer. The Journal of Supercomputing, 6 (1992) 237–255
Doallo, R., Touriño, J., Zapata, E.L.: Sparse Householder QR Factorization on a Mesh. In Fourth Euromicro Workshop on Parallel and Distributed Processing, Braga (Portugal), IEEE Computer Society Press (January 1996) 33–39
Touriño, J., Doallo, R., Zapata, E.L.: Sparse Givens QR Factorization on a Multiprocessor. In MPCS'96 (submitted)
Hare, D.R., Johnson, C.R., Olesky, D.D., Van Den Driessche, P.: Sparsity Analysis of the QR Factorization. SIAM J. Matrix Anal. Appl., 14(3) (July 1993) 655–669
Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Clarendon Press (1986)
Duff, I.S., Grimes, R.G., Lewis, J.G.: User's Guide for the Harwell-Boeing Sparse Matrix Collection. Technical Report TR-PA-92-96, CERFACS (October 1992)
Romero, L.F., Zapata, E.L.: Data Distributions for Sparse Matrix Vector Multiplication. Parallel Computing, 21(4) (1995) 583–605
Asenjo, R., Zapata, E.L.: Sparse LU Factorization on the Cray T3D. In Int'l Conference on High-Performance Computing and Networking, Milan (Italy), Springer-Verlag LNCS no.919 (May 1995) 690–696
Cray Research, Inc: Cray T3D. Technical Summary, (September 1993)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doallo, R., Fraguela, B.B., Touriño, J., Zapata, E.L. (1996). Parallel sparse modified Gram-Schmidt QR decomposition. In: Liddell, H., Colbrook, A., Hertzberger, B., Sloot, P. (eds) High-Performance Computing and Networking. HPCN-Europe 1996. Lecture Notes in Computer Science, vol 1067. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61142-8_609
Download citation
DOI: https://doi.org/10.1007/3-540-61142-8_609
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61142-4
Online ISBN: 978-3-540-49955-8
eBook Packages: Springer Book Archive