Artem Napov

We present a convergence analysis of a Galerkin‐type two‐grid method based on plain (or unsmoothed) aggregation. The analysis assumes that the system matrix is symmetric nonnegative definite (SNND) and can be decomposed into (or bounded below by) a sum of SNND matrices, each associated with an individual aggregate. Then, the convergence factor of the considered two‐grid method can be bounded above (up to the smoother's scaling) as a function of a maximum over all aggregates of a quantity associated to each aggregate and named aggregate's quality. The presented analysis is a generalization of the analysis from [A. Napov and Y. Notay, Numer. Linear Algebra Appl. 18(2011), pp. 539–564], and is suitable for finite element discretizations, for which the system matrix subdivision into element matrices is a natural starting point. The analysis is further applied in the context of standard finite element discretizations of linear elasticity problems. More specifically, we derive a sharp estimate of the quality parameter of a two‐node aggregate, that is, an aggregate containing all unknowns associated to two connected nodes of the discretization mesh. This estimate is given here as a function of the average stiffness tensor (which we do not assume isotropic), the vector connecting the nodes, the geometry of the elements containing both nodes and the diagonal entries of the system matrix corresponding to the nodes. Eventually, we illustrate the accuracy and usefulness of the presented bounds with some numerical experiments.

Two different approaches for the linear-time solution of three-dimensional magnetostatic field problems encompassing large-scale linear systems with millions of degrees of freedom are presented. The φ–method is formulated in terms of nodal variables, i.e., magnetic scalar potentials, and involves the solution of a curl-curl linear system for pre-processing and of a div-grad linear system. The A–method is formulated in terms of edge variables, i.e., line integrals of the magnetic vector potential, and involves the solution of a curl-curl linear system only. It is shown that these linear systems can be solved by flexible conjugate gradient in combination with the aggregation-based multigrid preconditioner AGMG, tailored for div-grad problems, and with the aggregation-based (auxiliary-space) multigrid preconditioner AGMG_CC, tailored for curlcurl problems. The robustness and efficiency of these solvers is illustrated using magnetostatic problems of practical interest, with linear or nonlinear media and having parts with complex geometry. Numerical results show that both AGMG and AGMG_CC are able to attain linear solution time in all cases considered, while being both faster and more robust than state-of-the-art algebraic multigrid solvers and SOR-preconditioned Krylov solvers, typically adopted in commercial software for electromagnetic analysis.

A hybrid a—φ Cell Method formulation for solving eddy–current problems in 3–D multiply–connected regions is presented. By using the magnetic scalar potential the number of degrees of freedom in the exterior domain with respect to the A, V—A formulation, typically implemented in commercial software for electromagnetic design, can be almost halved. On the other hand, the use of the magnetic vector potential in the interior domain improves the flexibility with respect to T–Ω formulation, since both conductive and magnetic parts can be easily modeled. By using a Cell Method variant, based on an augmented dual grid for discretization, electric and magnetic variables can be consistently coupled at the interface between interior and exterior domain. Global basis functions needed for representing the magnetic field in the insulating region are obtained by using for the first time iterative solvers relying on auxiliary space preconditioner and aggregation–based algebraic multigrid, with linear optimal complexity. These represent highly–efficient alternatives to traditional computational topology algorithms based on the concept of thick cut. As a result, an indefinite symmetric matrix system, amenable to fast iterative solution, is obtained. Numerical tests show high accuracy and fast convergence of the a—φ method on test cases with complex topology. Computational cost for both matrix assembly and linear system solution is limited even for large problems. Comparisons show that the a—φ method provides better performance than existing methods such as A, V—A and h—φ.

Electronic Transactions on Numerical Analysis (ETNA) is an electronic journal for the publication of significant new developments in numerical analysis and scientific computing. Papers of the highest quality that deal with the analysis of algorithms for the solution of continuous models and numerical linear algebra are appropriate for ETNA, as are papers of similar quality that discuss implementation and performance of such algorithms. New algorithms for current or new computer architectures are appropriate provided that they are numerically sound. However, the focus of the publication should be on the algorithm rather than on the architecture. The journal is published by the Kent State University Library in conjunction with the Institute of Computational Mathematics at Kent State University, and in cooperation with the Johann Radon Institute for Computational and Applied Mathematics of the Austrian Academy of Sciences (RICAM). Reviews of all ETNA papers appear in Mathematical Reviews and Zentralblatt für Mathematik. Reference information for ETNA papers also appears in the expanded Science Citation Index. ETNA is registered with the Library of Congress and has ISSN 1068-9613.

Electronic Transactions on Numerical Analysis (ETNA) is an electronic journal for the publication of significant new developments in numerical analysis and scientific computing. Papers of the highest quality that deal with the analysis of algorithms for the solution of continuous models and numerical linear algebra are appropriate for ETNA, as are papers of similar quality that discuss implementation and performance of such algorithms. New algorithms for current or new computer architectures are appropriate provided that they are numerically sound. However, the focus of the publication should be on the algorithm rather than on the architecture. The journal is published by the Kent State University Library in conjunction with the Institute of Computational Mathematics at Kent State University, and in cooperation with the Johann Radon Institute for Computational and Applied Mathematics of the Austrian Academy of Sciences (RICAM). Reviews of all ETNA papers appear in Mathematical Reviews and Zentralblatt für Mathematik. Reference information for ETNA papers also appears in the expanded Science Citation Index. ETNA is registered with the Library of Congress and has ISSN 1068-9613.

Summary: We present an algebraic structured preconditioner for the iterative solution of large sparse linear systems. The preconditioner is based on a multifrontal variant of sparse LU factorization used with nested dissection ordering. Multifrontal factorization amounts to a partial factorization of a sequence of logically dense frontal matrices, and the preconditioner is obtained if structured factorization is used instead. This latter exploits the presence of low numerical rank in some off‐diagonal blocks of the frontal matrices. An algebraic procedure is presented that allows to identify the hierarchy of the off‐diagonal blocks with low numerical rank based on the sparsity of the system matrix. This procedure is motivated by a model problem analysis, yet numerical experiments show that it is successful beyond the model problem scope. Further aspects relevant for the algebraic structured preconditioner are discussed and illustrated with numerical experiments. The preconditioner is also compared with other solvers, including the corresponding direct solver. Copyright © 2015 John Wiley & Sons, Ltd.

We investigate the use of algebraic multigrid (AMG) methods for the solution of large sparse linear systems arising from the discretization of scalar elliptic partial differential equations with Lagrangian finite elements of order at most 4. The resulting system matrices do not have the M-matrix property that is required by standard analyses of classical AMG and aggregation-based AMG methods. A unified approach is presented that allows us to extend these analyses. It uses an intermediate M-matrix and highlights the role of the spectral equivalence constant that relates this matrix to the original system matrix. This constant is shown to be bounded independently of the problem size and jumps in the coefficients of the partial differential equations, provided that jumps are located at elements' boundaries. For two-dimensional problems, it is further shown to be uniformly bounded if the angles in the triangulation also satisfy a uniform bound. This analysis validates the application of the AMG methods to the considered problems. On the other hand, because the intermediate M-matrix can be computed automatically, an alternative strategy is to define the AMG preconditioners from this matrix, instead of defining them from the original matrix. Numerical experiments are presented that assess both strategies using publicly available state-of-the-art implementations of classical AMG and aggregation-based AMG methods.