Keywords
Schwarz procedures, linear equations, partitions
Abstract
We describe a new algorithm designed to quickly and robustly solve general linear problems of the form Ax = b. We describe both serial and parallel versions of the algorithm, which can be considered a prioritized version of an Alternating Multiplicative Schwarz procedure. We also adopt a general view of alternating Multiplicative Schwarz procedures which motivates their use on arbitrary problems (even which may not have arisen from problems that are naturally decomposable) by demonstrating that, even in a serial context, algorithms should use many, many partitions to accelerate convergence; having such an over-partitioned system also allows easy parallelization of the algorithm, and scales extremely well. We present extensive empirical evidence which demonstrates that our algorithm, with a companion subsolver, can often improve performance by several orders of magnitude over the subsolver by itself and over other algorithms.
Original Publication Citation
Prioritized Multiplicative Schwarz Procedures for Solutions to General Linear Systems, David Wingate, Nathaniel Powell, Quinn Snell, Kevin Seppi, Proceedings of the 25 International Parallel and Distributed Processing Symposium, April 25.
BYU ScholarsArchive Citation
Powell, Nathaniel; Seppi, Kevin; Snell, Quinn O.; and Wingate, David, "Prioritized Multiplicative Schwarz Procedures for Solving Linear Systems" (2005). Faculty Publications. 388.
https://scholarsarchive.byu.edu/facpub/388
Document Type
Peer-Reviewed Article
Publication Date
2005-04-01
Permanent URL
http://hdl.lib.byu.edu/1877/2585
Publisher
IEEE
Language
English
College
Physical and Mathematical Sciences
Department
Computer Science
Copyright Status
© 2005 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Copyright Use Information
http://lib.byu.edu/about/copyright/