Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Massively parallel polar decomposition on distributed-memory systems
Ltaief H., Sukkari D., Esposito A., Nakatsukasa Y., Keyes D. ACM Transactions on Parallel Computing6 (1):1-15,2019.Type:Article
Date Reviewed: Oct 20 2020

For solving problems with high computational demands, it is nowadaysessential to apply parallel algorithms that scale effectively to a largenumber of computational cores: microprocessors may integrate dozens of cores,and compute clusters may combine thousands of processors. One such problemis the polar decomposition (PD) of a matrix, a linear algebra operation “requiredfor a broad class of scientific applications.” So far, this problem was mosteffectively solved by the QR-factorization-based dynamically weighted Halley(QDWH) algorithm that converges for double precision matrices in at most sixiterations.

This paper improves QDWH by utilizing special properties of the Zolotarev (ZOLO) functions underlying the iteration. The resulting ZOLO-PD algorithm derivesthe (2r+1)-th approximation of the solution from r independent QR factorizations; then, for r=8, convergence is achieved with only two iterations. Thus, ZOLO-PD exposes a much higher degree of parallelism than QDWH, but at the price of a higher total arithmetic complexity and a larger memory footprint. After a thorough description of the message passing interface (MPI) implementation of the algorithm, the paper then evaluates its actual performance: indeed, ZOLO-PD outperforms QDWH by afactor of two, but only for a sufficiently large amount of resources (800 nodes, 32 cores).

All in all, this represents a very informative case study on massivelyparallel algorithm design and the tradeoff between algorithmic complexityand inherent parallelism. The thorough evaluation of the algorithm is amodel for other researchers. Finally, the paper opens up new researchopportunities with respect to data movement optimization and dynamicscheduling to improve load balancing.

Reviewer:  Wolfgang Schreiner Review #: CR147086 (2102-0043)
Bookmark and Share
  Featured Reviewer  
 
Mathematical Software (G.4 )
 
 
Parallel Algorithms (G.1.0 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Mathematical Software": Date
Mathematical applications of electronic spreadsheets
Arganbright D., McGraw-Hill, Inc., New York, NY, 1984. Type: Book (9789780070024298)
May 1 1985
The NAG Library: a beginners guide
Phillips J., Oxford University Press, Inc., New York, NY, 1987. Type: Book (9789780198532637)
May 1 1988
Numerical software tools in C
Kempf J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1987. Type: Book (9789780136272748)
Apr 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy