More Like this

1. Structured Semidefinite Programming for Recovering Structured Preconditioners

   Jambulapati, Arun; Li, Jerry; Musco, Christopher; Shiragur, Kirankumar; Sidford, Aaron; Tian, Kevin (December 2023, Advances in Neural Information Processing Systems)

   We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving problems including the following. \begin{itemize} \item \textbf{Diagonal preconditioning.} We give an algorithm which, given positive definite $$\mathbf{K} \in \mathbb{R}^{d \times d}$$ with $$\mathrm{nnz}(\mathbf{K})$$ nonzero entries, computes an $$\epsilon$$-optimal diagonal preconditioner in time $$\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot \mathrm{poly}(\kappa^\star,\epsilon^{-1}))$$, where $$\kappa^\star$$ is the optimal condition number of the rescaled matrix. \item \textbf{Structured linear systems.} We give an algorithm which, given $$\mathbf{M} \in \mathbb{R}^{d \times d}$$ that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in $$\mathbf{M}$$ in $$\widetilde{O}(d^2)$$ time. \end{itemize} Our diagonal preconditioning results improve state-of-the-art runtimes of $$\Omega(d^{3.5})$$ attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of $$\Omega(d^{\omega})$$ where $$\omega > 2.3$$ is the current matrix multiplication constant. We attain our results via new algorithms for a class of semidefinite programs (SDPs) we call \emph{matrix-dictionary approximation SDPs}, which we leverage to solve an associated problem we call \emph{matrix-dictionary recovery}. 

   more » « less
2. Spike Variations for Stochastic Volterra Integral Equations

   https://doi.org/10.1137/22M1522097  

   Wang, Tianxiao; Yong, Jiongmin (December 2023, SIAM Journal on Control and Optimization)

   The spike variation technique plays a crucial role in deriving Pontryagin's type maximum principle of optimal controls for ordinary differential equations (ODEs), partial differential equations (PDEs), stochastic differential equations (SDEs), and (deterministic forward) Volterra integral equations (FVIEs), when the control domains are not assumed to be convex. It is natural to expect that such a technique could be extended to the case of (forward) stochastic Volterra integral equations (FSVIEs). However, by mimicking the case of SDEs, one encounters an essential difficulty of handling an involved quadratic term. To overcome this difficulty, we introduce an auxiliary process for which one can use It\^o's formula, and develop new technologies inspired by stochastic linear-quadratic optimal control problems. Then the suitable representation of the above-mentioned quadratic form is obtained, and the second-order adjoint equations are derived. Consequently, the maximum principle of Pontryagin type is established. Some relevant extensions are investigated as well. 

   more » « less
3. Preconditioning of the generalized Stokes problem arising from the approximation of the time-dependent Navier-Stokes equations

   https://doi.org/10.1016/j.camwa.2025.05.001  

   Creff, Melvin; Guermond, Jean-Luc (October 2025, Computers and Mathematics with Applications)

   The paper compares standard iterative methods for solving the generalized Stokes problem arising from the time and space approximation of the time-dependent incompressible Navier-Stokes equations. Various preconditioning techniques are considered: (1) pressure Schur complement; (2) fully coupled system using an exact factorization as a basis for the preconditioner; (3) fully coupled system using norm equivalence considerations as a basis for the preconditioner; (4) in all the cases we also investigate the benefits of the augmented Lagrangian formulation. Our objective is to see whether one of these methods can compete with traditional pressure-correction and velocity-correction methods in terms of throughput (the throughput is the ratio of the number of degrees of freedom of the problem divided by the number of cores and the wall-clock time in second). Numerical tests on fine unstructured meshes (68 millions degrees of freedoms) demonstrate GMRES/CG convergence rates that are independent of the mesh size and improve with the Reynolds number for most methods. Three conclusions are drawn: (1) The throughputs of all the methods tested in the paper are similar up to mesh-independent multiplicative constants (see Fig. 6). (2) Although very good parallel scalability is observed for the augmented Lagrangian version of the generalized Stokes problem, the best throughputs are achieved without the augmented Lagrangian term. (3) The throughput of all the methods tested in the paper is on average 5 to 25 times slower than that of traditional pressure-correction and velocity-correction methods (on average 5 for the best one). Hence, although all these methods are very efficient for solving steady state problems, pressure- 

   more » « less
4. A field‐split preconditioning technique for fluid‐structure interaction problems with applications in biomechanics

   https://doi.org/10.1002/cnm.3301  

   Calandrini, Sara; Aulisa, Eugenio; Ke, Guoyi (April 2020, International Journal for Numerical Methods in Biomedical Engineering)

   Abstract We present a novel preconditioning technique for Krylov subspace algorithms to solve fluid‐structure interaction (FSI) linearized systems arising from finite element discretizations. An outer Krylov subspace solver preconditioned with a geometric multigrid (GMG) algorithm is used, where for the multigrid level subsolvers, a field‐split (FS) preconditioner is proposed. The block structure of the FS preconditioner is derived using the physical variables as splitting strategy. To solve the subsystems originated by the FS preconditioning, an additive Schwarz (AS) block strategy is employed. The proposed FS preconditioner is tested on biomedical FSI applications. Both 2D and 3D simulations are carried out considering aneurysm and venous valve geometries. The performance of the FS preconditioner is compared with that of a second preconditioner of pure domain decomposition type. 

   more » « less
5. Interior over-penalized enriched Galerkin methods for second order elliptic equations

   https://doi.org/10.1016/j.camwa.2023.09.049  

   Lee, Jeonghun J; Ghattas, Omar (December 2023, Computers & Mathematics with Applications)

   In this paper we propose a variant of enriched Galerkin methods for second order elliptic equations with over-penalization of interior jump terms. The bilinear form with interior over-penalization gives a non-standard norm which is different from the discrete energy norm in the classical discontinuous Galerkin methods. Nonetheless we prove that optimal a priori error estimates with the standard discrete energy norm can be obtained by combining a priori and a posteriori error analysis techniques. We also show that the interior over-penalization is advantageous for constructing preconditioners robust to mesh refinement by analyzing spectral equivalence of bilinear forms. Numerical results are included to illustrate the convergence and preconditioning results. 

   more » « less