For my work supporting Bifrost, a programming environment built for visual effects artists, I am seeking a good “default” preconditioner for solving linear systems or accelerating nonlinear solvers in problems arising in physics simulation and geometric problems. Narrowing the focus, I’m looking particularly at large, sparse, symmetric-positive definite matrices with either an explicit or implied sum-of-squares structure, most notably finite element stiffness matrices for elliptic problems. On the other hand, I do not want to make further assumptions such as the signs of off-diagonal nonzeros, whether the vector of all ones plays a special role, etc. which may break down in the face of situations such as biharmonic-like shell problems and matrix rescalings to avoid unnecessary ill-conditioning. In this talk, I’ll discuss my current experiments with preconditioners inspired by Shklarski and Toledo’s “fretsaw extension”, itself based on ideas from support graph preconditioning. Rather than viewing this as a way to approximate the graph of the original matrix with a tree plus a few extra edges (which implies an efficient exact Cholesky factorization), I introduce two new ideas:
1) sparsification viewed as partial assembly of the stiffness matrix, guided by exactly what an efficient Cholesky factorization needs, and
2) adding constraints to the semi-assembled system to keep it equivalent to the original problem, rather than just an approximation.
While the constrained semi-assembled system cannot be efficiently factored in its entirety, it opens up more avenues for how to approach preconditioning, which hopefully will lead to the desired solver characteristics.