Nicole Spillane

Pierre Matalon, Nicole Spillane

The convergence of the GMRES linear solver is notoriously hard to predict. A particularly enlightening result by [Greenbaum, Pták, Strakoš, 1996] is that, given any convergence curve, one can build a linear system for which GMRES realizes that convergence curve. What is even more extraordinary is that the eigenvalues of the problem matrix can be chosen arbitrarily. We build upon this idea to derive novel results about weighted GMRES. We prove that for any linear system and any prescribed convergence curve, there exists a weight matrix M for which weighted GMRES (i.e., GMRES in the inner product induced by M) realizes that convergence curve, and we characterize the form of M. Additionally, we exhibit a necessary and sufficient condition on M for the simultaneous prescription of two convergence curves, one realized by GMRES in the Euclidean inner product, and the other in the inner product induced by M. These results are then applied to infer some properties of preconditioned GMRES when the preconditioner is applied either on the left or on the right. For instance, we show that any two convergence curves are simultaneously possible for left and right preconditioned GMRES.

Elise Fressart, Michel Nowak, Nicole Spillane

Even in cases where quantum linear solvers provide significant speedup compared to their classical counterparts, their performance depends on some of the same parameters. In particular, the condition number of the matrix which is to be inverted is a decisive parameter. A well known classical, and now quantum, remedy is to precondition the linear system $A x = b$ by premultiplying it by a matrix $H$ in such a way that the condition number of $HA$ is significantly smaller than the condition number of $A$. In this work, we focus on a family of preconditioners called domain decomposition. First, we prove that it is feasible to apply quantum domain decomposition. We provide upper bounds for the block-encoding parameters of the Poisson problem discretized by the finite element method and preconditioned by the two-level Additive Schwarz preconditioner (one of the most fundamental domain decomposition techniques). From these bounds, we deduce the complexity of the quantum linear system solver. Second, we focus on a particular choice of local solver within the domain decomposition preconditioner by applying recent work by [Deiml and Peterseim, \textit{Math. Comput.}, 2025] on the Bramble--Pasciak--Xu (BPX) preconditioner. Finally, we provide details on how the operators are implemented.