Cao Lu

Aditi Ghai, Cao Lu, Xiangmin Jiao

Preconditioned Krylov subspace (KSP) methods are widely used for solving large-scale sparse linear systems arising from numerical solutions of partial differential equations (PDEs). These linear systems are often nonsymmetric due to the nature of the PDEs, boundary or jump conditions, or discretization methods. While implementations of preconditioned KSP methods are usually readily available, it is unclear to users which methods are the best for different classes of problems. In this work, we present a comparison of some KSP methods, including GMRES, TFQMR, BiCGSTAB, and QMRCGSTAB, coupled with three classes of preconditioners, namely Gauss-Seidel, incomplete LU factorization (including ILUT, ILUTP, and multilevel ILU), and algebraic multigrid (including BoomerAMG and ML). Theoretically, we compare the mathematical formulations and operation counts of these methods. Empirically, we compare the convergence and serial performance for a range of benchmark problems from numerical PDEs in 2D and 3D with up to millions of unknowns and also assess the asymptotic complexity of the methods as the number of unknowns increases. Our results show that GMRES tends to deliver better performance when coupled with an effective multigrid preconditioner, but it is less competitive with an ineffective preconditioner due to restarts. BoomerAMG with proper choice of coarsening and interpolation techniques typically converges faster than ML, but both may fail for ill-conditioned or saddle-point problems while multilevel ILU tends to succeed. We also show that right preconditioning is more desirable. This study helps establish some practical guidelines for choosing preconditioned KSP methods and motivates the development of more effective preconditioners.

Cao Lu, Tristan Delaney, Xiangmin Jiao

Saddle-point systems appear in many scientific and engineering applications. The systems can be sparse, symmetric or nonsymmetric, and possibly singular. In many of these applications, the number of constraints is relatively small compared to the number of unknowns. The traditional null-space method is inefficient for these systems, because it is expensive to find the null space explicitly. Some alternatives, notably constraint-preconditioned or projected Krylov methods, are relatively efficient, but they can suffer from numerical instability and even nonconvergence. In addition, most existing methods require the system to be nonsingular or be reducible to a nonsingular system. In this paper, we propose a new method, called OPINS, for singular and nonsingular saddle-point systems. OPINS is equivalent to the null-space method with an orthogonal projector, without forming the orthogonal basis of the null space explicitly. OPINS can not only solve for the unique solution for nonsingular saddle-point problems, but also find the minimum-norm solution in terms of the solution variables for singular systems. The method is efficient and easy to implement using existing Krylov solvers for singular systems. At the same time, it is more stable than the other alternatives, such as projected Krylov methods. We present some preconditioners to accelerate the convergence of OPINS for nonsingular systems, and compare OPINS against some present state-of-the-art methods for various types of singular and nonsingular systems.