Descent Iterations for Improving Approximate Eigenpairs of Polynomial Eigenvalue Problems with General Complex Matrices

In this paper, we consider descent iterations with line search for improving an approximate eigenvalue and a corresponding approximate eigenvector of polynomial eigenvalue problems with general complex matrices, where an approximate eigenpair was obtained by some method. The polynomial eigenvalue problem is written as a system of complex nonlinear equations with nondifferentiable normalized condition. Convergence theorems for iterations are established. Finally, some numerical examples are presented to demonstrate the effectiveness of the iterative methods. Received April 9, 2001; revised October 2, 2001 Published online February 18, 2002     

On the Convergence Rate of a Preconditioned Subspace Eigensolver

In this paper we present a proof of convergence for a preconditioned subspace method which shows the dependency of the convergence rate on the preconditioner used. This convergence rate depends only on the condition of the pre-conditioned system and the relative separation of the first two eigenvalues . This means that, for example, multigrid preconditioners can be used to find eigenvalues of elliptic PDE's at a grid-independent rate. Received: March 9, 1999, revised June 23, 1999     

Solution of Large Scale Algebraic Matrix Riccati Equations by Use of Hierarchical Matrices

In previous papers, a class of hierarchical matrices (ℋ-matrices) is introduced which are data-sparse and allow an approximate matrix arithmetic of almost optimal complexity. Here, we investigate a new approach to exploit the ℋ-matrix structure for the solution of large scale Lyapunov and Riccati equations as they typically arise for optimal control problems where the constraint is a partial differential equation of elliptic type. This approach leads to an algorithm of linear-logarithmic complexity in the size of the matrices. Received July 30, 2002; revised December 16, 2002 Published online: April 22, 2003     

Incomplete Block Triangular Decompositions of Order l

In this paper, we present a special technique for improving the robustness of block triangular decompositions, for example those described in [1], that have proved their efficiency as preconditioners for the conjugate gradient method in a wide class of problems. The thorough theoretical analysis of this technique is carried out for the model problem, and the practical efficiency in the case of more complex problems is illustrated by numerical examples. Received August 2, 1999; revised September 21, 1999     

Extension of the Thomas Algorithm to a Class of Algebraic Linear Equation Systems Involving Quasi-Block-Tridiagonal Matrices with Isolated Block-Pentadiagonal Rows, Assuming Variable Block Dimensions

Received July 17, 2000; revised January 31, 2001     

The Streamline–Diffusion Method for Conforming and Nonconforming Finite Elements of Lowest Order Applied to Convection–Diffusion Problems

We consider the streamline-diffusion finite element method with finite elements of lowest order for solving convection-diffusion problems. Our investigations cover both conforming and nonconforming finite element approximations on triangular and quadrilateral meshes. Although the considered finite elements are of the same interpolation order their stability and approximation properties are quite different. We give a detailed overview on the stability and the convergence properties in the L ²- and in the streamline–diffusion norm. Numerical experiments show that often the theoretical predictions on the convergence properties are sharp. Received December 7, 1999; revised October 5, 2000     

A Dynamic Method for Weighted Linear Least Squares Problems

A new method for solving the weighted linear least squares problems with full rank is proposed. Based on the theory of Liapunov's stability, the method associates a dynamic system with a weighted linear least squares problem, whose solution we are interested in and integrates the former numerically by an A-stable numerical method. The numerical tests suggest that the new method is more than comparative with current conventional techniques based on the normal equations. Received August 4, 2000; revised August 29, 2001 Published online April 25, 2002     

A Sparse Matrix Arithmetic Based on \Cal H-Matrices. Part I: Introduction to {\Cal H}-Matrices

A class of matrices (-matrices) is introduced which have the following properties. (i) They are sparse in the sense that only few data are needed for their representation. (ii) The matrix-vector multiplication is of almost linear complexity. (iii) In general, sums and products of these matrices are no longer in the same set, but their truncations to the -matrix format are again of almost linear complexity. (iv) The same statement holds for the inverse of an -matrix. This paper is the first of a series and is devoted to the first introduction of the -matrix concept. Two concret formats are described. The first one is the simplest possible. Nevertheless, it allows the exact inversion of tridiagonal matrices. The second one is able to approximate discrete integral operators. Received: July 30, 1998; revised December 28, 1998     

Incomplete Cross Approximation in the Mosaic-Skeleton Method

The mosaic-skeleton method was bred in a simple observation that rather large blocks in very large matrices coming from integral formulations can be approximated accurately by a sum of just few rank-one matrices (skeletons). These blocks might correspond to a region where the kernel is smooth enough, and anyway it can be a region where the kernel is approximated by a short sum of separable functions (functional skeletons). Since the effect of approximations is like that of having small-rank matrices, we find it pertinent to say about mosaic ranks of a matrix which turn out to be pretty small for many nonsingular matrices. On the first stage, the method builds up an appropriate mosaic partitioning using the concept of a tree of clusters and some extra information rather than the matrix entries (related to the mesh). On the second stage, it approximates every allowed block by skeletons using the entries of some rather small cross which is chosen by an adaptive procedure. We focus chiefly on some aspects of practical implementation and numerical examples on which the approximation time was found to grow almost linearly in the matrix size. Received February 13, 1999; revised October 26, 1999     

A Multigrid Method for Nonconforming FE-Discretisations with Application to Non-Matching Grids

Nonconforming finite element discretisations require special care in the construction of the prolongation and restriction in the multigrid process. In this paper, a general scheme is proposed, which guarantees the approximation property. As an example, the technique is applied to the discretisation by non-matching grids (mortar elements). Received: October 15, 1998     

Adaptive Low-Rank Approximation of Collocation Matrices

This article deals with the solution of integral equations using collocation methods with almost linear complexity. Methods such as fast multipole, panel clustering and ℋ-matrix methods gain their efficiency from approximating the kernel function. The proposed algorithm which uses the ℋ-matrix format, in contrast, is purely algebraic and relies on a small part of the collocation matrix for its blockwise approximation by low-rank matrices. Furthermore, a new algorithm for matrix partitioning that significantly reduces the number of blocks generated is presented. Received August 15, 2002; revised September 20, 2002 Published online: March 6, 2003     

Nitsche Type Mortaring for some Elliptic Problem with Corner Singularities

The paper deals with Nitsche type mortaring as a finite element method (FEM) for treating non-matching meshes of triangles at the interface of some domain decomposition. The approach is applied to the Poisson equation with Dirichlet boundary conditions (as a model problem) under the aspect that the interface passes re-entrant corners of the domain. For such problems and non-matching meshes with and without local refinement near the re-entrant corner, some properties of the finite element scheme and error estimates are proved. They show that appropriate mesh grading yields convergence rates as known for the classical FEM in presence of regular solutions. Finally, a numerical example illustrates the approach and the theoretical results. Received July 5, 2001; revised February 5, 2002 Published online April 25, 2002     

Runge Kutta Type Methods for Isodynamical Matrix Flows: Applications to Balanced Realizations

Recently several numerical methods have been proposed for solving isospectral problems which are matrix differential systems whose solutions preserve the spectrum during the evolution. In this paper we consider matrix differential systems called isodynamical flows in which only a component of the matrix solution preserves the eigenvalues during the evolution and we propose procedures for their numerical solution. Applications of such numerical procedures may be found in systems theory, in particular in balancing realization problems. Several numerical tests will be reported. Received April 27, 2001; revised October 25, 2001 Published online February 18, 2002     

Fundamental Systems of Numerical Schemes for Linear Convection–Diffusion Equations and their Relationship to Accuracy

A new approach towards the assessment and derivation of numerical methods for convection dominated problems is presented, based on the comparison of the fundamental systems of the continuous and discrete operators. In two or more space dimensions, the dimension of the fundamental system is infinite, and may be identified with a ball. This set is referred to as the true fundamental locus. The fundamental system for a numerical scheme also forms a locus. As a first application, it is shown that a necessary condition for the uniform convergence of a numerical scheme is that the discrete locus should contain the true locus, and it is then shown it is impossible to satisfy this condition with a finite stencil. This shows that results of Shishkin concerning non-uniform convergence at parabolic boundaries are also generic for outflow boundaries. It is shown that the distance between the loci is related to the accuracy of the schemes provided that the loci are sufficiently close. However, if the loci depart markedly, then the situation is rather more complicated. Under suitable conditions, we develop an explicit numerical lower bound on the attainable relative error in terms of the coefficients in the stencil characterising the scheme and the loci. Received December 10, 1999; revised August 14, 2000     

Multilevel Approximation of Boundary Integral Operators

Received March 29, 2000; revised June 7, 2001     

A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

We propose a cascadic multigrid algorithm for a semilinear indefinite elliptic problem. We use a standard finite element discretization with piecewise linear finite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within sufficiently high precision without substantial computational effort. On each finer grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a sufficiently fine initial grid and for a sufficiently good start approximation the algorithm yields an approximate solution within the discretization error on the finest grid and that the method has multigrid complexity with logarithmic multiplier. Received February 1999, revised July 13, 1999     

A Class of Smoothers for Saddle Point Problems

In this paper smoothing properties are shown for a class of iterative methods for saddle point problems with smoothing rates of the order 1/m, where m is the number of smoothing steps. This generalizes recent results by Braess and Sarazin, who could prove this rates for methods where, in the context of the Stokes problem, the pressure correction equation is solved exactly, which is not needed here. Received December 4, 1998; revised April 14, 2000     

Variable Additive Preconditioning Procedures

Iterative methods with variable preconditioners of additive type are proposed. The scaling factors of each summand in the additive preconditioners are optimized within each iteration step. It is proved that the presented methods converge at least as fast as the Richardson's iterative method with the corresponding additive preconditioner with optimal scaling factors. In the presented numerical experiments the suggested methods need nearly the same number of iterations as the usual preconditioned conjugate gradient method with the corresponding additive preconditioner with numerically determined fixed optimal scaling factors. Received: June 10, 1998; revised October 16, 1998     

Multilevel Gauging for Edge Elements

The vector potential of a solenoidal vector field, if it exists, is not unique in general. Any procedure that aims to determine such a vector potential typically involves a decision on how to fix it. This is referred to by the term gauging. Gauging is an important issue in computational electromagnetism, whenever discrete vector potentials have to be computed. In this paper a new gauging algorithm for discrete vector potentials is introduced that relies on a hierarchical multilevel decomposition. With minimum computational effort it yields vector potentials whose L ²-norm does not severely blow up. Thus the new approach compares favorably to the widely used co-tree gauging. Received May 27, 1999; revised October 22, 1999     

Application of an Adaptive Sparse-Grid Technique to a Model Singular Perturbation Problem

In this paper we show how, under minimal conditions, a combination extrapolation can be introduced for an adaptive sparse grid. We apply this technique for the solution of a two-dimensional model singular perturbation problem, defined on the domain exterior of a circle. Received October 18, 1999