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
Uniform block-diagonal preconditioners for divergence-conforming HDG Methods for the generalized Stokes equations and the linear elasticity equations
Abstract We propose a uniform block-diagonal preconditioner for condensed $H$(div)-conforming hybridizable discontinuous Galerkin schemes for parameter-dependent saddle point problems, including the generalized Stokes equations and the linear elasticity equations. An optimal preconditioner is obtained for the stiffness matrix on the global velocity/displacement space via the auxiliary space preconditioning technique (Xu (1994) The Auxiliary Space Method and Optimal Multigrid Preconditioning Techniques for Unstructured Grids, vol. 56. International GAMM-Workshop on Multi-level Methods (Meisdorf), pp. 215–235). A spectrally equivalent approximation to the Schur complement on the element-wise constant pressure space is also constructed, and an explicit computable exact inverse is obtained via the Woodbury matrix identity. Finally, the numerical results verify the robustness of our proposed preconditioner with respect to model parameters and mesh size.
more »
« less
- Award ID(s):
- 2012031
- NSF-PAR ID:
- 10451756
- Date Published:
- Journal Name:
- IMA Journal of Numerical Analysis
- Volume:
- 43
- Issue:
- 3
- ISSN:
- 0272-4979
- Page Range / eLocation ID:
- 1718 to 1741
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
more » « less
Summary In this work, we provide new analysis for a preconditioning technique called structured incomplete factorization (SIF) for symmetric positive definite matrices. In this technique, a scaling and compression strategy is applied to construct SIF preconditioners, where off‐diagonal blocks of the original matrix are first scaled and then approximated by low‐rank forms. Some spectral behaviors after applying the preconditioner are shown. The effectiveness is confirmed with the aid of a type of two‐dimensional and three‐dimensional discretized model problems. We further show that previous studies on the robustness are too conservative. In fact, the practical multilevel version of the preconditioner has a robustness enhancement effect, and is unconditionally robust (or breakdown free) for the model problems regardless of the compression accuracy for the scaled off‐diagonal blocks. The studies give new insights into the SIF preconditioning technique and confirm that it is an effective and reliable way for designing structured preconditioners. The studies also provide useful tools for analyzing other structured preconditioners. Various spectral analysis results can be used to characterize other structured algorithms and study more general problems.
-
more » « less
Abstract The ongoing transition to coupled data assimilation (DA) systems encounters substantial technical difficulties associated with the need to merge together different elements of atmospheric and ocean DA systems that typically have had independent development paths for decades. In this study, we consider the incorporation of strong coupling in the observation space via successive corrections that involve the application of only uncoupled solvers to a sequence of innovation vectors. The coupled increment is then obtained by projecting a coupled innovation vector on the grid using coupled ensemble correlations. The proposed approach is motivated by the classic block Jacobi matrix iteration applied to the coupled system using the uncoupled solvers as a preconditioner. The method is tested via numerical experiments with the CERA ensemble in a simplified setting.
-
more » « less
Abstract It is known that the solutions to space‐fractional diffusion equations exhibit singularities near the boundary. Therefore, numerical methods discretized on the composite mesh, in which the mesh size is refined near the boundary, provide more precise approximations to the solutions. However, the coefficient matrices of the corresponding linear systems usually lose the diagonal dominance and are ill‐conditioned, which in turn affect the convergence behavior of the iteration methods.In this work we study a finite volume method for two‐sided fractional diffusion equations, in which a locally refined composite mesh is applied to capture the boundary singularities of the solutions. The diagonal blocks of the resulting three‐by‐three block linear system are proved to be positive‐definite, based on which we propose an efficient block Gauss–Seidel method by decomposing the whole system into three subsystems with those diagonal blocks as the coefficient matrices. To further accelerate the convergence speed of the iteration, we use T. Chan's circulant preconditioner31as the corresponding preconditioners and analyze the preconditioned matrices' spectra. Numerical experiments are presented to demonstrate the effectiveness and the efficiency of the proposed method and its strong potential in dealing with ill‐conditioned problems. While we have not proved the convergence of the method in theory, the numerical experiments show that the proposed method is convergent.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imanum/drac021
