Speaker
Description
Design problems such as topology optimization and PDE-based inverse problems require the solution of a sequence of linear-systems derived from finite element or finite difference discretization. Preconditioning is essential for the fast solution of these systems by iterative methods. However, computing an accurate preconditioner for every system in the sequence may be a computational bottleneck, warranting a cheap preconditioner-updating scheme. The sparse approximate map (SAM), introduced in Preconditioning Parametrized Linear Systems by Carr et al. (SISC 2021), computes a sparse approximation of the exact map between matrices in the sequence. Each column of the SAM is computed by solving a small least-squares problem. The resulting map can be leveraged to update a preconditioner computed earlier in the sequence. This method is cheap as long as the underlying sparsity pattern has few non-zeros. However, as revealed in prior research, often there is no intuitive best choice for such a pattern. Often the sparsity pattern of the matrix (or powers of it) can be used, but for topology optimization matrices or for high-order finite element stiffness matrices with a large number of non-zeros per column this is a poor choice. In this talk, we show how generating patterns using an L-1 constrained least squares solve (lasso) can be very effective. We solve the lasso problem to modest accuracy using the alternating direction method of multipliers (ADMM). We demonstrate that the parameters of ADMM and the regularization parameter can be heuristically selected to compute matrix maps that are significantly sparse and sufficiently accurate. This is joint work with Johann Rudi and Eric de Sturler.