article

Free access

Optimal algorithms for parallel Givens factorization on a coarse-grained PRAM

Authors:

Michel Cosnard,

El Mostafa DaoudiAuthors Info & Claims

Journal of the ACM (JACM), Volume 41, Issue 2

Pages 399 - 421

https://doi.org/10.1145/174652.174660

Published: 01 March 1994 Publication History

PDF eReader

References

[1]

~COSNARD, M., AND ROBERT, Y. 1983. Complexitd de la factorisation QR en parallale. C. R. Acad. ~Sci. Paris 297/t, 549-552.

Google Scholar

[2]

~COSNARD, M., AND ROBERT, Y. 1986. Complexity of parallel QR decomposition. J. ACM 33, 4 ~(Oct.), 712 723.

Crossref

Google Scholar

[3]

~COSNARD, M., MULLER, J. M., AND ROBERT, Y. 1986. Parallel QR decomposition of a rectangu- ~lar matrix. Numen Math. 48, 239-249.

Crossref

Google Scholar

[4]

~DAOUDI, E. M. 1989. Etude de la complexit~ de la d~composition orthogonale d'une matrice sur ~plusieurs modbles d'architectures parallales. Th~se de I'INP Grenoble. mai.

Google Scholar

[5]

~HELLER, D. 1978. A survey of parallel algorithms in numerical linear algebra. SIAM Ret,iew 20, ~740-777.

Google Scholar

[6]

~LORD, R. E., KOWALIK, J. S., AND KUMAR, S. P. 1983. Solving linear algebraic equations on an ~MIMD computer. J. ACM 30, l (Jan.), 103-117.

Crossref

Google Scholar

[7]

~MOD1, J. J., AND CLARKE, M. R. B. 1984. An alternative Givens ordering. Numer. Math. 43, ~83-90.

Google Scholar

[8]

~SAMEH, A., AND KUCK, D. 1978. On stable parallel linear system solvers. J. ACM 25, 1 (Jan.), ~ 81-91.

Crossref

Google Scholar

Cited By

View all

Hofmann MKontoghiorghes E(2018)Pipeline Givens sequences for computing the QR decomposition on a EREW PRAMParallel Computing10.1016/j.parco.2005.11.00132:3(222-230)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/j.parco.2005.11.001
Tiskin A(2018)Communication-efficient parallel generic pairwise eliminationFuture Generation Computer Systems10.1016/j.future.2006.04.01723:2(179-188)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.future.2006.04.017
Kontoghiorghes E(2018)Greedy givens algorithms for computing the rank-k updating of the QR decompositionParallel Computing10.1016/S0167-8191(02)00132-128:9(1257-1273)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/S0167-8191%2802%2900132-1
Show More Cited By

Index Terms

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 ...
Dynamic ordering for a parallel block-Jacobi SVD algorithm
Parallel matrix algorithms and applications

A new approach for the parallel computation of singular value decomposition (SVD) of matrix A ∈ C^m×n is proposed. Contrary to the known algorithms that use a static cyclic ordering of subproblems simultaneously solved in one iteration step, the proposed ...
On General Row Merging Schemes for Sparse Givens Transformations

This paper introduces general row merging schemes for the $QR$ decomposition of sparse matrices by Givens rotations. They can be viewed as a generalization of row rotations to submatrix rotations (or merging) in the recent method by George and Heath [12]...

Reviews

Reviewer: Jonathan Samuel Golan

The authors study the complexity of various parallel implementations of the Givens method for the orthogonal decomposition of an m×n matrix on a PRAM where the read, compute, and write operations are done on vectors, and where the number p of processors is fixed in advance. For square matrices of size n×n , an asymptotically optimal algorithm is constructed with time complexity equal to T opt p = n 2 2p +p+o n for 1?p?n p+ 2 -1+o n .

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 41, Issue 2

March 1994

230 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/174652

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1994

Published in JACM Volume 41, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
472
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)7

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hofmann MKontoghiorghes E(2018)Pipeline Givens sequences for computing the QR decomposition on a EREW PRAMParallel Computing10.1016/j.parco.2005.11.00132:3(222-230)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/j.parco.2005.11.001
Tiskin A(2018)Communication-efficient parallel generic pairwise eliminationFuture Generation Computer Systems10.1016/j.future.2006.04.01723:2(179-188)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.future.2006.04.017
Kontoghiorghes E(2018)Greedy givens algorithms for computing the rank-k updating of the QR decompositionParallel Computing10.1016/S0167-8191(02)00132-128:9(1257-1273)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/S0167-8191%2802%2900132-1
(2018)Load balanced parallel QR decomposition on shared memory multiprocessorsParallel Computing10.1016/S0167-8191(01)00087-427:10(1321-1345)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/S0167-8191%2801%2900087-4
Gallopoulos EPhilippe BSameh AGallopoulos EPhilippe BSameh A(2015)Orthogonal Factorization and Linear Least Squares ProblemsParallelism in Matrix Computations10.1007/978-94-017-7188-7_7(227-247)Online publication date: 26-Jul-2015
https://doi.org/10.1007/978-94-017-7188-7_7
Tiskin A(2003)Communication-Efficient Parallel Gaussian EliminationParallel Computing Technologies10.1007/978-3-540-45145-7_35(369-383)Online publication date: 2003
https://doi.org/10.1007/978-3-540-45145-7_35
Foschi PGarin LKontoghiorghes E(2002)Numerical and Computational Strategies for Solving Seemingly Unrelated Regression ModelsComputational Methods in Decision-Making, Economics and Finance10.1007/978-1-4757-3613-7_21(405-427)Online publication date: 2002
https://doi.org/10.1007/978-1-4757-3613-7_21
KONTOGHIORGHES E(2000)PARALLEL GIVENS SEQUENCES FOR SOLVING THE GENERAL LINEAR MODEL ON A EREW PRAM∗Parallel Algorithms and Applications10.1080/0149573000894735015:1-2(57-75)Online publication date: Jun-2000
https://doi.org/10.1080/01495730008947350
Kontoghiorghes E(1999)Ordinary linear model estimation on a massively parallel SIMD computerConcurrency: Practice and Experience10.1002/(SICI)1096-9128(199906)11:7<323::AID-CPE425>3.0.CO;2-I11:7(323-341)Online publication date: Jun-1999
https://doi.org/10.1002/(SICI)1096-9128(199906)11:7<323::AID-CPE425>3.0.CO;2-I
Bhuvaneswari KSiva Ram murthy C(1998)A fault tolerant systolic mesh for linear system solutionInternational Journal of Computer Mathematics10.1080/0020716980880466767:3-4(315-332)Online publication date: Jan-1998
https://doi.org/10.1080/00207169808804667
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Highly Scalable Parallel Algorithms for Sparse Matrix Factorization

Dynamic ordering for a parallel block-Jacobi SVD algorithm

On General Row Merging Schemes for Sparse Givens Transformations

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations