ROW REPLICATED BLOCK CIMMINO.

We study a new technique for reducing the number of iterations of the block Cimmino method by replicating rows in the partitioned system, so that we obtain a nondisjoint partitioning of the rows. Since rows in different partitions that are close to colinear produce a poorly conditioned iteration matrix for the block Cimmino method, row replication can get around this problem. With intelligent replication choices, we can reduce the number of iterations for convergence of the replicated block Cimmino method. The downside is a slight increase of the computational workload associated with each partition. In order to find a trade-off between a lower number of iterations and a higher cost per iteration, selecting the proper set of rows for replication is crucial. In this paper, we use graph-based techniques to find good candidates for replication. Since the block Cimmino method can be interpreted as a nonoverlapping additive Schwartz method applied to the normal equations, the replication techniques correspond to introducing an overlap between the subdomains defined by the partitions. We show analytically in the case of a two-block partitioning how the replication improves the condition number of the block Cimmino iteration matrix. We then use challenging two-dimensional PDE problems to show that our algebraic approach targets physically meaningful phenomena on the interface between partitions. We demonstrate the efficiency of the proposed method in improving the performance of the block Cimmino solver, even with a small amount of replication, on problems from the SuiteSparse Matrix Collection. Finally, we compare our approach to a BiCGStab preconditioned with an additive Schwartz method and show that our replication technique can be used to define the subdomains and overlaps in the context of domain decomposition methods. [ABSTRACT FROM AUTHOR]