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.
(c) 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.;