Multiscale Linear Solvers for Very Large Systems Derived from PDES

DOI10.1137/S1064827598339785MaRDI QIDQ4509810zbMATH OpenFDO

Authors K. S. Lackner, Ralph Menikoff

Publication date 19 October 2000

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9809043

zbMATH Keywords

algorithmconjugate gradientGauss-Seidel splittingitertive splittingJacobi splittingmultigridmultiscalingnumerical examplesporous flow equationpreconditioningwavelength decomposition

Mathematics Subject Classification ID

Boundary value problems for second-order elliptic equations (35J25) Iterative numerical methods for linear systems (65F10) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Flows in porous media; filtration; seepage (76S05)

Abstract: We present a novel linear solver that works well for large systems obtained from discretizing PDEs. It is robust and, for the examples we studied, the computational effort scales linearly with the number of equations. The algorithm is based on a wavelength decomposition that combines conjugate gradient, multi-scaling and iterative splitting methods into a single approach. On the surface, the algorithm is a simple preconditioned conjugate gradient with all the sophistication of the algorithm in the choice of the preconditioning matrix. The preconditioner is a very good approximate inverse of the linear operator. It is constructed from the inverse of the coarse grained linear operator and from smoothing operators that are based on an operator splitting on the fine grid. The coarse graining captures the long wavelength behavior of the inverse operator while the smoothing operator captures the short wavelength behavior. The conjugate gradient iteration accounts for the coupling between long and short wavelengths. The coarse grained operator corresponds to a lowerresolution approximation to the PDEs. While the coarse grained inverse is not known explicitly, the algorithm only requires that the preconditioner can be a applied to a vector. The coarse inverse applied to a vector can be obtained as the solution of another preconditioned conjugate gradient solver that applies the same algorithm to the smaller problem. Thus, the method is naturally recursive. The recursion ends when the matrix is sufficiently small for a solution to be obtained efficiently with a standard solver. We have tested our solver on the porous flow equation. On a workstation we have solved problems on grids ranging in dimension from $10^3$ to $10^6$, and found that the linear scaling holds.

Recommendations

• Preconditioning of conjugate gradients by multigrid solver
• Multigrid method with preconditioning on coarse level
• scientific article; zbMATH DE number 1323248
• Domain decomposition and multigrid solvers for flow simulation in porous media on distributed memory parallel processors
• Element Preconditioning Using Splitting Techniques

Cited in

(3)

• A numerical study on large-scale nonlinear solvers
• A preconditioned, multilevel mimetic finite difference method for solving the pressure-velocity system
• A SOLVER OF LINEAR SYSTEMS OF EQUATIONS (REBSM) FOR LARGE-SCALE ENGINEERING PROBLEMS

This page was built for publication: Multiscale Linear Solvers for Very Large Systems Derived from PDES

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4509810)