Semi-Unstructured Grids

We present a novel automatic grid generator for the finite element discretization of partial differential equations in 3D. The grids constructed by this grid generator are composed of a pure tensor product grid in the interior of the domain and an unstructured grid which is only contained in boundary cells. The unstructured component consists of tetrahedra, each of which satisfies a maximal interior angle condition. By suitable constructing the boundary cells, the number of types of boundary subcells is reduced to 12 types. Since this grid generator constructs large structured grids in the interior and small unstructured grids near the boundary, the resulting semi-unstructured grids have similar properties as structured tensor product grids. Some appealing properties of this method are computational efficiency and natural construction of coarse grids for multilevel algorithms. Numerical results and an analysis of the discretization error are presented. Received July 17, 2000; revised October 27, 2000     

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 Predictor for Lossless Image Compression

A new method for lossless image compression of grey-level images is proposed. The image is treated as a set of stacked bit planes. The compressed version of the image is represented by residuals of a non-linear local predictor spanning the current bit plane as well as a few neighbouring ones. Predictor configurations are grouped in pairs differing in one bit of the representative point only. The frequency of predictor configurations is obtained from the input image. The predictor adapts automatically to the image, it is able to estimate the influence of neighbouring cells and thus copes even with complicated structure or fine texture. The residuals between the original and the predicted image are those that correspond to the less frequent predictor configurations. Efficiently coded residuals constitute the output image. To our knowledge, the performance of the proposed compression algorithm is comparable to the current state of the art. Especially good results were obtained for binary images, grey-level cartoons and man-made drawings. Received: June 29, 1998; revised November 2, 1998     

A Modification of Newton's Method for Analytic Mappings Having Multiple Zeros

We propose a modification of Newton's method for computing multiple roots of systems of analytic equations. Under mild assumptions the iteration converges quadratically. It involves certain constants whose product is a lower bound for the multiplicity of the root. As these constants are usually not known in advance, we devise an iteration in which not only an approximation for the root is refined, but also approximations for these constants. Numerical examples illustrate the effectiveness of our approach. Received: August 17, 1998     

Partial Linearization of One Class of the Nonlinear Total Least Squares Problem by Using the Inverse Model Function

In this paper we consider a special nonlinear total least squares problem, where the model function is of the form . Using the fact that after an appropriate substitution, the model function becomes linear in parameters, and that the symmetry preserves the distances, this nonlinear total least squares problem can be greatly simplified. In this paper we give the existence theorem, propose an efficient algorithm for searching the parameters and give some numerical examples. Received: June 30, 1997; revised October 31, 1998     

Condition Numbers of Approximate Schur Complements in Two- and Three-Dimensional Discretizations on Hierarchically Ordered Grids

We investigate multilevel incomplete factorizations of M-matrices arising from finite difference discretizations. The nonzero patterns are based on special orderings of the grid points. Hence, the Schur complements that result from block elimination of unknowns refer to a sequence of hierarchical grids. Having reached the coarsest grid, Gaussian elimination yields a complete decomposition of the last Schur complement. The main focus of this paper is a generalization of the recursive five-point/nine-point factorization method (which can be applied in two-dimensional problems) to matrices that stem from discretizations on three-dimensional cartesian grids. Moreover, we present a local analysis that considers fundamental grid cells. Our analysis allows to derive sharp bounds for the condition number associated with one factorization level (two-grid estimates). A comparison in case of the Laplace operator with Dirichlet boundary conditions shows: Estimating the relative condition number of the multilevel preconditioner by multiplying corresponding two-grid values gives the asymptotic bound O(h ^−0.347) for the two- respectively O(h ^−4/5) for the three-dimensional model problem. Received October 19, 1998; revised September 27, 1999     

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     

Sufficient Conditions for Uniform Convergence on Layer-Adapted Grids

We study convergence properties of the simple upwind difference scheme and a Galerkin finite element method on generalized Shishkin grids. We derive conditions on the mesh-characterizing function that are sufficient for the convergence of the method, uniformly with respect to the perturbation parameter. These conditions are easy to check and enable one to immediately deduce the rate of convergence. Numerical experiments support these theoretical results and indicate that the estimates are sharp. The analysis is set in one dimension, but can be easily generalized to tensor product meshes in 2D. Received: December 21, 1998; revised March 17, 1999     

Inexact Methods in the Numerical Solution of Stiff Initial Value Problems

Inexact Newton methods can be effectively used in codes for large stiff initial value problems for ordinary differential equations. In this paper we give a new convergence result for Inexact Newton methods. Further, we indicate how this general result can be used and actually implemented to obtain an efficient code for solving stiff initial value problems. Received: March 12, 1998; revised March 31, 1999     

Preconditioners for Solving Stochastic Boundary Integral Equations with Weakly Singular Kernels

A stochastic linear heat conduction problem is reduced to a special weakly singular integral equation of the second kind. The smoothness of the solution to a multidimensional weakly singular integral equation is investigated. It is also indicated that the derivatives of solutions may have singularities of certain order near the boundary of domain. The solution in the form of a multidimensional cubic spline is studied using circulant integral operators and a special mesh near the boundary with respect to all variables. Furthermore, stable numerical algorithms are given. Received: June 22, 1998; revised November 11, 1998     

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     

An Algorithm and Fortran Program for Multivariate LAD ℓ (ℓ1 of ℓ2) Regression

A FORTRAN package is presented for multivariate Least sum of Absolute Deviations (LAD) regression with respect to the ℓ₁ of ℓ₂ norm, and this regression method is compared with ℓ₂ of ℓ₂ regression and ℓ₁ of ℓ₁ regression. Applications of the algorithm include multivariate permutation analyses of experimental design and prediction models which are based on Euclidean distance. Received April 15, 1998; revised October 25, 2001 Published online February 18, 2002     

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     

Weighted Mean of a Pair of Graphs

G and G′, with d(G, G′) being the edit distance of G and G′, the weighted mean of G and G′ is a graph G″ that has edit distances d(G, G″) and d(G″, G′) to G and G′, respectively, such that d(G, G″) + d(G″, G′) = d(G,G′). We'll show formal properties of the weighted mean, describe a procedure for its computation, and give examples. Received April 9, 2001     

Parallel Processing Strategies for Large SAR Image Data Sets in a Distributed Environment

Image processing of synthetic aperture radar (SAR) images is challenging due to distributed storage of input data sets and since appropriate algorithms are complex and time-consuming. Computers able to process these data in acceptable time usually are not at user's site. Our Concurrent and Distributed Image Processing (CDIP) system overcomes these problems and provides a platform-independent, transparent environment based on Java, CORBA and NetSolve. Users query a broker to find remote, high-performance servers on which the algorithms actually are executed. Key algorithms like image matching and Shape-from-Shading were parallelized mainly using MPI, and ported onto suitable computer architectures. Our experiments showed that all algorithms perform well, and they further proved the concept of CDIP to be beneficial: Usability of all integrated algorithms was significantly improved, mainly due to less user-centered network traffic, simple access to supercomputers, the creation of method sequences, and easy-to-use and well maintained algorithms. Received: June 10, 1998; revised November 16, 1998     

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     

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     

High Accuracy Analysis of the Adini's Nonconforming Element

Received September 14, 2000; revised September 25, 2001     

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     

Horner's Rule for Interval Evaluation Revisited

Interval arithmetic can be used to enclose the range of a real function over a domain. However, due to some weak properties of interval arithmetic, a computed interval can be much larger than the exact range. This phenomenon is called dependency problem. In this paper, Horner's rule for polynomial interval evaluation is revisited. We introduce a new factorization scheme based on well-known symbolic identities in order to handle the dependency problem of interval arithmetic. The experimental results show an improvement of 25% of the width of computed intervals with respect to Horner's rule. Received December 14, 2001; revised March 27, 2002 Published online: July 8, 2002