29 Matching Results

Search Results

Advanced search parameters have been applied.

Coarse Spaces by Algebraic Multigrid: Multigrid Convergence and Upscaled Error Estimates

Description: We give an overview of a number of algebraic multigrid methods targeting finite element discretization problems. The focus is on the properties of the constructed hierarchy of coarse spaces that guarantee (two-grid) convergence. In particular, a necessary condition known as 'weak approximation property', and a sufficient one, referred to as 'strong approximation property' are discussed. Their role in proving convergence of the TG method (as iterative method) and also on the approximation properties of the AMG coarse spaces if used as discretization tool is pointed out. Some preliminary numerical results illustrating the latter aspect are also reported.
Date: April 30, 2010
Creator: Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Lecture Notes on Multigrid Methods

Description: The Lecture Notes are primarily based on a sequence of lectures given by the author while been a Fulbright scholar at 'St. Kliment Ohridski' University of Sofia, Sofia, Bulgaria during the winter semester of 2009-2010 academic year. The notes are somewhat expanded version of the actual one semester class he taught there. The material covered is slightly modified and adapted version of similar topics covered in the author's monograph 'Multilevel Block-Factorization Preconditioners' published in 2008 by Springer. The author tried to keep the notes as self-contained as possible. That is why the lecture notes begin with some basic introductory matrix-vector linear algebra, numerical PDEs (finite element) facts emphasizing the relations between functions in finite dimensional spaces and their coefficient vectors and respective norms. Then, some additional facts on the implementation of finite elements based on relation tables using the popular compressed sparse row (CSR) format are given. Also, typical condition number estimates of stiffness and mass matrices, the global matrix assembly from local element matrices are given as well. Finally, some basic introductory facts about stationary iterative methods, such as Gauss-Seidel and its symmetrized version are presented. The introductory material ends up with the smoothing property of the classical iterative methods and the main definition of two-grid iterative methods. From here on, the second part of the notes begins which deals with the various aspects of the principal TG and the numerous versions of the MG cycles. At the end, in part III, we briefly introduce algebraic versions of MG referred to as AMG, focusing on classes of AMG specialized for finite element matrices.
Date: June 28, 2010
Creator: Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Mesh independent convergence of the modified inexact Newton method for a second order nonlinear problem

Description: In this paper, we consider an inexact Newton method applied to a second order nonlinear problem with higher order nonlinearities. We provide conditions under which the method has a mesh-independent rate of convergence. To do this, we are required to first, set up the problem on a scale of Hilbert spaces and second, to devise a special iterative technique which converges in a higher than first order Sobolev norm. We show that the linear (Jacobian) system solved in Newton's method can be replaced with one iterative step provided that the initial nonlinear iterate is accurate enough. The closeness criteria can be taken independent of the mesh size. Finally, the results of numerical experiments are given to support the theory.
Date: September 20, 2004
Creator: Kim, T; Pasciak, J E & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Parallel auxiliary space AMG for definite Maxwell problems

Description: Motivated by the needs of large multi-physics simulation codes, we are interested in algebraic solvers for the linear systems arising in time-domain electromagnetic simulations. Our focus is on finite element discretization, and we are developing scalable parallel preconditioners which employ only fine-grid information, similar to algebraic multigrid (AMG) for diffusion problems. In the last few years, the search for efficient algebraic preconditioners for H(curl) bilinear forms has intensified. The attempts to directly construct AMG methods had some success, see [12, 1, 7]. Exploiting available multilevel methods on auxiliary mesh for the same bilinear form led to efficient auxiliary mesh preconditioners to unstructured problems as shown in [4, 8]. A computationally more attractive approach was recently proposed by Hiptmair and Xu [5]. In contrast to the auxiliary mesh idea, the method in [5] uses a nodal H{sup 1}-conforming auxiliary space on the same mesh. This significantly simplifies the computation of the corresponding interpolation operator. In the present talk, we consider several options for constructing unstructured mesh AMG preconditioners for H(curl) problems and report a summary of computational results from [10, 9]. Our approach is slightly different than the one from [5], since we apply AMG directly to variationally constructed coarse-grid operators, and therefore no additional Poisson matrices are needed on input. We also consider variable coefficient problems, including some that lead to a singular matrix. Both type of problems are of great practical importance and are not covered by the theory of [5].
Date: February 16, 2007
Creator: Kolev, T V & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Direction-Preserving and Schur-Monotonic Semi-Separable Approximations of Symmetric Positive Definite Matrices}

Description: For a given symmetric positive definite matrix A {element_of} R{sup N x N}, we develop a fast and backward stable algorithm to approximate A by a symmetric positive-definite semi-separable matrix, accurate to a constant multiple of any prescribed tolerance. In addition, this algorithm preserves the product, AZ, for a given matrix Z {element_of} R{sup N x d}, where d << N. Our algorithm guarantees the positive-definiteness of the semi-separable matrix by embedding an approximation strategy inside a Cholesky factorization procedure to ensure that the Schur complements during the Cholesky factorization all remain positive definite after approximation. It uses a robust direction-preserving approximation scheme to ensure the preservation of AZ. We present numerical experiments and discuss potential implications of our work.
Date: March 16, 2010
Creator: Gu, M; Li, X S & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Exact de Rham Sequences of Spaces Defined on Macro-elements in Two and Three Spatial Dimensions

Description: This paper proposes new finite element spaces that can be constructed for agglomerates of standard elements that have certain regular structure. The main requirement is that the agglomerates share faces that have closed boundaries composed of 1-d edges. The spaces resulting from the agglomerated elements are subspaces of the original de Rham sequence of H{sup 1}-conforming, H(curl) conforming, H(div) conforming and piecewise constant spaces associated with an unstructured 'fine' mesh. The procedure can be recursively applied so that a sequence of nested de Rham complexes can be constructed. As an illustration we generate coarser spaces from the sequence corresponding to the lowest order Nedelec spaces, lowest order Raviart-Thomas spaces, and for piecewise linear H{sup 1}-conforming spaces, all in three-dimensions. The resulting V-cycle multigrid methods used in preconditioned conjugate gradient iterations appear to perform similar to those of the geometrically refined case.
Date: July 23, 2007
Creator: Pasciak, J. & Vassilevski, P.
Partner: UNT Libraries Government Documents Department

Parallel eigensolver for H(curl) problems using H1-auxiliary space AMG preconditioning

Description: This report describes an application of the recently developed H{sup 1}-auxiliary space preconditioner for H(curl) problems to the Maxwell eigenvalue problem. The auxiliary space method based on the new (HX) finite element space decomposition introduced in [7], was implemented in the hypre library, [10, 11] under the name AMS. The eigensolver considered in the present paper, referred to as the AME, is an extension of the AMS. It is based on the locally optimal block eigensolver LOBPCG [9] and the parallel AMG (algebraic multigrid) solver BoomerAMG [2] from the hypre library. AME is designed to compute a block of few minimal nonzero eigenvalues and eigenvectors, for general unstructured finite element discretizations utilizing the lowest order Nedelec elements. The main goal of the current report is to document the usage of AME and to illustrate its parallel scalability.
Date: November 15, 2006
Creator: Kolev, T V & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Parallel H1-based auxiliary space AMG solver for H(curl) problems

Description: This report describes a parallel implementation of the auxiliary space methods for definite Maxwell problems proposed in [4]. The solver, named AMS, extends our previous study [7]. AMS uses ParCSR sparse matrix storage and the parallel AMG (algebraic multigrid) solver BoomerAMG [1] from the hypre library. It is designed for general unstructured finite element discretizations of (semi)definite H(curl) problems discretized by Nedelec elements. We document the usage of AMS and illustrate its parallel scalability and overall performance.
Date: June 30, 2006
Creator: Kolev, T V & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

On Some Versions of the Element Agglomeration AMGe Method

Description: The present paper deals with element-based AMG methods that target linear systems of equations coming from finite element discretizations of elliptic PDEs. The individual element information (element matrices and element topology) is the main input to construct the AMG hierarchy. We study a number of variants of the spectral agglomerate element based AMG method. The core of the algorithms relies on element agglomeration utilizing the element topology (built recursively from fine to coarse levels). The actual selection of the coarse degrees of freedom (dofs) is based on solving large number of local eigenvalue problems. Additionally, we investigate strategies for adaptive AMG as well as multigrid cycles that are more expensive than the V-cycle utilizing simple interpolation matrices and nested conjugate gradient (CG) based recursive calls between the levels. The presented algorithms are illustrated with an extensive set of experiments based on a matlab implementation of the methods.
Date: August 9, 2007
Creator: Lashuk, I & Vassilevski, P
Partner: UNT Libraries Government Documents Department

Multiple Vector Preserving Interpolation Mappings in Algebraic Multigrid

Description: We propose algorithms for the construction of AMG (algebraic multigrid) interpolation mappings such that the resulting coarse space to span (locally and globally) any number of a priori given set of vectors. Specific constructions in the case of element agglomeration AMG methods are given. Some numerical illustration is also provided.
Date: November 3, 2004
Creator: Vassilevski, P S & Zikatanov, L T
Partner: UNT Libraries Government Documents Department

Convergence Analysis of a Domain Decomposition Paradigm

Description: We describe a domain decomposition algorithm for use in several variants of the parallel adaptive meshing paradigm of Bank and Holst. This algorithm has low communication, makes extensive use of existing sequential solvers, and exploits in several important ways data generated as part of the adaptive meshing paradigm. We show that for an idealized version of the algorithm, the rate of convergence is independent of both the global problem size N and the number of subdomains p used in the domain decomposition partition. Numerical examples illustrate the effectiveness of the procedure.
Date: June 12, 2006
Creator: Bank, R E & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

AMG by element agglomeration and constrained energy minimization interpolation

Description: This paper studies AMG (algebraic multigrid) methods that utilize energy minimization construction of the interpolation matrices locally, in the setting of element agglomeration AMG. The coarsening in element agglomeration AMG is done by agglomerating fine-grid elements, with coarse element matrices defined by a local Galerkin procedure applied to the matrix assembled from the individual fine-grid element matrices. This local Galerkin procedure involves only the coarse basis restricted to the agglomerated element. To construct the coarse basis, one exploits previously proposed constraint energy minimization procedures now applied to the local matrix. The constraints are that a given set of vectors should be interpolated exactly, not only globally, but also locally on every agglomerated element. The paper provides algorithmic details, as well as a convergence result based on a ''local-to-global'' energy bound of the resulting multiple-vector fitting AMG interpolation mappings. A particular implementation of the method is illustrated with a set of numerical experiments.
Date: February 17, 2006
Creator: Kolev, T V & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Space-Time Approximation with Sparse Grids

Description: In this article we introduce approximation spaces for parabolic problems which are based on the tensor product construction of a multiscale basis in space and a multiscale basis in time. Proper truncation then leads to so-called space-time sparse grid spaces. For a uniform discretization of the spatial space of dimension d with O(N{sup d}) degrees of freedom, these spaces involve for d > 1 also only O(N{sup d}) degrees of freedom for the discretization of the whole space-time problem. But they provide the same approximation rate as classical space-time Finite Element spaces which need O(N{sup d+1}) degrees of freedoms. This makes these approximation spaces well suited for conventional parabolic and for time-dependent optimization problems. We analyze the approximation properties and the dimension of these sparse grid space-time spaces for general stable multiscale bases. We then restrict ourselves to an interpolatory multiscale basis, i.e. a hierarchical basis. Here, to be able to handle also complicated spatial domains {Omega}, we construct the hierarchical basis from a given spatial Finite Element basis as follows: First we determine coarse grid points recursively over the levels by the coarsening step of the algebraic multigrid method. Then, we derive interpolatory prolongation operators between the respective coarse and fine grid points by a least squares approach. This way we obtain an algebraic hierarchical basis for the spatial domain which we then use in our space-time sparse grid approach. We give numerical results on the convergence rate of the interpolation error of these spaces for various space-time problems with two spatial dimensions. Also implementational issues, data structures and questions of adaptivity are addressed to some extent.
Date: April 14, 2005
Creator: Griebel, M; Oeltz, D & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

Overlapping Schwarz for Nonlinear Problems. An Element Agglomeration Nonlinear Additive Schwarz Preconditioned Newton Method for Unstructured Finite Element Problems

Description: This paper extends previous results on nonlinear Schwarz preconditioning ([4]) to unstructured finite element elliptic problems exploiting now nonlocal (but small) subspaces. The non-local finite element subspaces are associated with subdomains obtained from a non-overlapping element partitioning of the original set of elements and are coarse outside the prescribed element subdomain. The coarsening is based on a modification of the agglomeration based AMGe method proposed in [8]. Then, the algebraic construction from [9] of the corresponding non-linear finite element subproblems is applied to generate the subspace based nonlinear preconditioner. The overall nonlinearly preconditioned problem is solved by an inexact Newton method. Numerical illustration is also provided.
Date: February 10, 2005
Creator: Cai, X C; Marcinkowski, L & Vassilevski, P S
Partner: UNT Libraries Government Documents Department

A Generalized Eigensolver based on Smoothed Aggregation (GES-SA) for Initializing Smoothed Aggregation Multigrid (SA)

Description: Consider the linear system Ax = b, where A is a large, sparse, real, symmetric, and positive definite matrix and b is a known vector. Solving this system for unknown vector x using a smoothed aggregation multigrid (SA) algorithm requires a characterization of the algebraically smooth error, meaning error that is poorly attenuated by the algorithm's relaxation process. For relaxation processes that are typically used in practice, algebraically smooth error corresponds to the near-nullspace of A. Therefore, having a good approximation to a minimal eigenvector is useful to characterize the algebraically smooth error when forming a linear SA solver. This paper discusses the details of a generalized eigensolver based on smoothed aggregation (GES-SA) that is designed to produce an approximation to a minimal eigenvector of A. GES-SA might be very useful as a standalone eigensolver for applications that desire an approximate minimal eigenvector, but the primary aim here is for GES-SA to produce an initial algebraically smooth component that may be used to either create a black-box SA solver or initiate the adaptive SA ({alpha}SA) process.
Date: May 31, 2007
Creator: Brezina, M; Manteuffel, T; McCormick, S; Ruge, J; Sanders, G & Vassilevski, P S
Partner: UNT Libraries Government Documents Department