TY - GEN A1 - Yserentant, Harry T1 - Two Preconditioners Based on the Multi-Level Splitting of Finite Element Spaces. N2 - The hierarchical basis preconditioner and the recent preconditioner of BRAMBLE, PASCIAK and XU are derived and analyzed within a joint framework. This discussion elucidates the close relationship between both methods. Special care is devoted to highly nonuniform meshes; our theory is based exclusively on local properties like the shape regularity of the finite elements. T3 - ZIB-Report - SC-89-09 Y1 - 1989 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-274 ER - TY - GEN A1 - Bank, Randolph A1 - Dupont, Todd F. A1 - Yserentant, Harry T1 - The Hierarchical Basis Multigrid Method. N2 - We derive and analyze the hierarchical basis-multigrid method for solving discretizations of self-adjoint, elliptic boundary value problems using piecewise linear triangular finite elements. The method is analyzed as a block symmetric Gauß- Seidel iteration with inner iterations, but it is strongly related to 2-level methods, to the standard multigrid V-cycle, and to earlier Jacobi-like hierarchical basis methods. The method is very robust, and has a nearly optimal convergence rate and work estimate. It is especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes. T3 - ZIB-Report - SC-87-02 KW - hierarchical basis KW - multigrid KW - finite elements KW - adaptive mesh refinement KW - preconditioned conjugate gradient methods KW - symmetric Gauss-Seidel Y1 - 1987 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44 ER - TY - GEN A1 - Yserentant, Harry T1 - Preconditioning Indefinite Discretization Matrices. N2 - The finite element discretization of many elliptic boundary value problems leads to linear systems with positive definite and symmetric coefficient matrices. Many efficient preconditioners are known for these systems. We show that these preconditioning matrices can be used also for the linear systems arising from boundary value problems which are potentially indefinite due to lower order terms in the partial differential equation. Our main tool is a careful algebraic analysis of the condition numbers and the spectra of perturbed matrices which are preconditioned by the same matrices as in the unperturbed case. {\bf Keywords: }Preconditioned conjugate gradient methods, finite elements. {\bf Subject Classification: } AMS(MOS):65F10, 65N20, 65N30. T3 - ZIB-Report - SC-87-06 KW - preconditioned conjugate gradient methods KW - finite elements Y1 - 1987 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81 ER - TY - GEN A1 - Schenk, Olaf A1 - Wächter, Andreas A1 - Weiser, Martin T1 - Inertia Revealing Preconditioning For Large-Scale Nonconvex Constrained Optimization N2 - Fast nonlinear programming methods following the all-at-once approach usually employ Newton's method for solving linearized Karush-Kuhn-Tucker (KKT) systems. In nonconvex problems, the Newton direction is only guaranteed to be a descent direction if the Hessian of the Lagrange function is positive definite on the nullspace of the active constraints, otherwise some modifications to Newton's method are necessary. This condition can be verified using the signs of the KKT's eigenvalues (inertia), which are usually available from direct solvers for the arising linear saddle point problems. Iterative solvers are mandatory for very large-scale problems, but in general do not provide the inertia. Here we present a preconditioner based on a multilevel incomplete $LBL^T$ factorization, from which an approximation of the inertia can be obtained. The suitability of the heuristics for application in optimization methods is verified on an interior point method applied to the CUTE and COPS test problems, on large-scale 3D PDE-constrained optimal control problems, as well as 3D PDE-constrained optimization in biomedical cancer hyperthermia treatment planning. The efficiency of the preconditioner is demonstrated on convex and nonconvex problems with $150^3$ state variables and $150^2$ control variables, both subject to bound constraints. T3 - ZIB-Report - 07-32 KW - nonconvex constrained optimization KW - interior-point method KW - inertia KW - multilevel incomplete factorization Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10314 SN - 1438-0064 ER - TY - GEN A1 - Walter, Artur T1 - Improvement of Incomplete Factorizations by a Sparse Secant Method. N2 - In the present paper, the improvement of an incomplete factorization of a non-symmetric matrix A is discussed. Starting from the ideas of sparsity preserving quasi-Newton methods, an algorithm is developed which improves the approximation of A by the incomplete factorization maintaining the sparsity structure of the matrices. No renumbering of the unknowns or the admittance of additional fill-in is necessary. The linear convergence of the algorithm is proved under the assumption, that $ L $ and $ U $* have the same sparsity structure and an incomplete factorization with some reasonable approximation property exits. In combination with this algorithm, the method of incomplete factorization and its several modifications are applicable to a wider class of problems with improved convergence qualities. This is shown by a numerical example. {\bf Key Words:} non-symmetric linear system, sparse secant method, incomplete factorization. AMS(MOS) {\bf Subject Classifications:} 65F10, 65N20, 65N30. T3 - ZIB-Report - SC-90-12 KW - non-symmetric linear systems KW - sparse secant method KW - incomplete factorization Y1 - 1990 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-401 ER - TY - GEN A1 - Beck, Rudolf T1 - Graph-Based Algebraic Multigrid for Lagrange-Type Finite Elements on Simplicial Meshes N2 - We present an algebraic multigrid preconditioner which uses only the graphs of system matrices. Some elementary coarsening rules are stated, from which an advancing front algorithm for the selection of coarse grid nodes is derived. This technique can be applied to linear Lagrange-type finite element discretizations; for higher-order elements an extension of the multigrid algorithm is provided. Both two- and three-dimensional second order elliptic problems can be handled. Numerical experiments show that the resulting convergence acceleration is comparable to classical geometric multigrid. T3 - ZIB-Report - SC-99-22 KW - Algebraic multigrid KW - mesh coarsening KW - preconditioning Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4100 ER - TY - GEN A1 - Deuflhard, Peter A1 - Freund, R. A1 - Walter, Artur T1 - Fast Secant Methods for the Iterative Solution of Large Nonsymmetric Linear Systems. N2 - A family of secant methods based on general rank-1 updates has been revisited in view of the construction of iterative solvers for large non- Hermitian linear systems. As it turns out, both Broydens "good" and "bad" update techniques play a special role - but should be associated with two different line search principles. For Broydens "bad" update technique, a minimum residual principle is natural - thus making it theorectically comparable with a series of well-known algorithms like GMRES. Broydens "good" update technique, however, is shown to be naturally linked with a minimum "next correction" principle - which asymptotically mimics a minimum error principle. The two minimization principles differ significantly for sufficiently large system dimension. Numerical experiments on discretized PDE's of convection diffusion type in 2-D with internal layers give a first impression of the possible power of the derived "good" Broyden variant. {\bf Key Words:} nonsymmetric linear system, secant method, rank-1 update, Broydens method, line search, GMRES. AMS(MOS) {\bf Subject Classifications:} 65F10, 65N20. T3 - ZIB-Report - SC-90-05 KW - nonsymmetric linear systems KW - secant method KW - rank-1 update KW - Broyden's method KW - line search KW - GMRES Y1 - 1990 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-330 ER - TY - GEN A1 - Deuflhard, Peter A1 - Leinen, P. A1 - Yserentant, Harry T1 - Concepts of an Adaptive Hierarchical Finite Element Code. N2 - The paper presents the mathematical concepts underlying the new adaptive finite element code KASKADE, which, in its present form, applies to linear scalar second-order 2-D elliptic problems on general domains. Starting point for the new development is the recent work on hierarchical finite element bases due to Yserentant (1986). It is shown that this approach permits a flexible balance between iterative solver, local error estimator, and local mesh refinement device - which are the main components of an adaptive PDE code. Without use of standard multigrid techniques, the same kind of computational complexity is achieved - independent of any uniformity restrictions on the applied meshes. In addition, the method is extremely simple and all computations are purely local - making the method particularly attractive in view of parallel computing. The algorithmic approach is illustrated by a well-known critical test problem. {\bf Keywords:} finite elements, hierarchical basis, adaptive mesh refinement, preconditioned conjugate gradient methods. T3 - ZIB-Report - SC-88-05 KW - finite elements KW - hierarchical basis KW - adaptive mesh refinement KW - preconditioned conjugate gradient methods Y1 - 1988 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-131 ER - TY - GEN A1 - Bornemann, Folkmar A. T1 - An Adaptive Multilevel Approach to Parabolic Equations III. N2 - Part III of the paper is devoted to the construction of an adaptive FEM solver in two spatial dimensions, which is able to handle the singularly perturbed elliptic problems arising from discretization in time. The problems of error estimation and multilevel iterative solution of the linear systems - both uniformly well behaved with respect to the time step - can be solved simultaneously within the framework of preconditioning. A multilevel nodal basis preconditioner able to handle highly nonuniform meshes is derived. As a numerical example an application of the method to the bioheat-transfer equation is included. {\bf AMS CLASSIFICATION:} 65F10, 65F35, 65M50, 65M60, 65N30. T3 - ZIB-Report - SC-91-01 Y1 - 1991 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-519 ER - TY - GEN A1 - Beck, Rudolf T1 - Algebraic Multigrid by Component Splitting for Edge Elements on Simplicial Triangulations N2 - Our focus is on Maxwell's equations in the low frequency range; two specific applications we aim at are time-stepping schemes for eddy current computations and the stationary double-curl equation for time-harmonic fields. We assume that the computational domain is discretized by triangles or tetrahedrons; for the finite element approximation we choose N\'{e}d\'{e}lec's $H(curl)$-conforming edge elements of the lowest order. For the solution of the arising linear equation systems we devise an algebraic multigrid preconditioner based on a spatial component splitting of the field. Mesh coarsening takes place in an auxiliary subspace, which is constructed with the aid of a nodal vector basis. Within this subspace coarse grids are created by exploiting the matrix graphs. Additionally, we have to cope with the kernel of the $curl$-operator, which comprises a considerable part of the spectral modes on the grid. Fortunately, the kernel modes are accessible via a discrete Helmholtz decomposition of the fields; they are smoothed by additional algebraic multigrid cycles. Numerical experiments are included in order to assess the efficacy of the proposed algorithms. T3 - ZIB-Report - SC-99-40 KW - Algebraic multigrid KW - mesh coarsening KW - edge elements KW - N\'{e}d\'{e}lec spaces KW - Maxwell's equations Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4290 ER -