By Edmond Chow and Kees Vuik
The subject of preconditioning, which encompasses techniques that help accelerate the convergence of iterative linear solvers, is already decades old. Yet the design and study of preconditioners seems constantly fresh as it continues to address problems from new application domains, adapts to new computer architectures, and incorporates ideas from new fields.
Preconditioning research is inherently interdisciplinary; therefore, the design of preconditioners must often be closely tied to the applications from which the equations arise, which poses a challenge for the field. No black box preconditioners work well for all problems, and preconditioning researchers must substantially understand domain applications to exploit the structure and properties of the matrices that emerge from them.
Figure 1. Hierarchical low-rank structure of a sample matrix. Brighter colors correspond to higher rank. Figure courtesy of Lucas Erlandson.
Some of the newest applications that demand preconditioners to address large-scale instances do not originate directly from partial differential equations (PDEs). For example, problems based on integral equation formulations, Gaussian process regression, and biomolecular simulations give rise to matrices whose entries represent the interactions between sets of points. When the interactions—defined by so-called kernel functions—are long-ranged, the matrices are dense but possess intriguing hierarchical low-rank structure, sometimes called data sparsity (see Figure 1). Fast linear-time matrix-vector multiplication algorithms are applicable for matrices with such structure, thus making iterative solution methods a viable choice. Some solution methods exist for certain types of rank-structured matrices—which could act as preconditioners—but otherwise the issue of preconditioning for these problems is new ground for exploration.
Although preconditioning traditionally applied only to linear systems of equations, it is now proving useful in the context of nonlinear equations. Few current ideas pertain to a nonlinear equation’s transformation into an equivalent one that is more rapidly solvable by a Newton method. Mathematician Martin Gander suggests viewing nonlinear preconditioning as a fixed-point iteration but employing Newton’s method to solve the equations at the fixed point (rather than using the fixed-point iteration as a solver). This is akin to taking the Jacobi or Gauss-Seidel fixed-point iterations and utilizing their splittings as preconditioners for Krylov subspace methods in the linear case.
Like other algorithms that must run efficiently on parallel computers, preconditioning has constantly adapted to new computer architectures. Graphics processing units (GPUs) and other hardware accelerators have high compute and memory bandwidth capabilities, but the question on how to efficiently use this hardware for the sparse computations typically required in preconditioning remains open. New preconditioning algorithms may very well need to exploit low-precision computational units available on the newest GPUs; because preconditioners are approximate anyway, computing and applying them in low precision is a possibility.
Designing preconditioners for realistic problems is sometimes as much an art as it is a science. Scientists have used machine learning to choose from the many options for preconditioners and select any necessary parameters. One could also possibly use machine learning to construct preconditioners him/herself. Early applications of neural networks included solving the linear systems from discretized PDEs, but these were quite primitive. It remains to be seen how machine learning can provide techniques where preconditioning theory is lacking for many realistic and complex problems.
These are just some of the issues that researchers are considering in the new decade. As preconditioning techniques are established for specific problems, domain scientists are demanding preconditioning for larger problems, more complicated physics, and novel problems altogether. This continuous cycle has kept preconditioning research active and alive. Preconditioning presents numerous opportunities to help accelerate the myriad of computational tools that advance science and engineering.
The International Conference on Preconditioning Techniques for Scientific and Industrial Applications, to be held in summer 2021 at the Chemnitz University of Technology in Germany, should be of interest to those in the field.
Edmond Chow is an associate professor in the School of Computational Science and Engineering at the Georgia Institute of Technology. He previously held positions at D. E. Shaw Research and Lawrence Livermore National Laboratory. Kees Vuik is a professor of numerical analysis at the Delft University of Technology. His expertise is the development of new preconditioners and high-performance computing.