On the Multivariate Horner Scheme II: Running Error Analysis

 As an extension of our previous paper which gave forward and backward error estimates, we perform a running error analysis of the multivariate Horner scheme. This leads to a modified algorithm which computes the value of the polynomial together with an error estimate. Received November 9, 1999; revised May 29, 2000     

Multiresolution Visualization of Higher Order Adaptive Finite Element Simulations

h –p–adaptive projection with respect to any prescribed threshold value for the visual error. This projection can then be processed by various local rendering methods, e.g. color coding of data or isosurface extraction. Especially for color coding purposes modern texture capabilities are used to directly render higher polynomial data by superposition of polynomial basis function textures and final color look-up tables. Numerical experiments from CFD clearly demonstrate the applicability and efficiency of our approach. Received September 25, 2001; revised March 31, 2003 Published online: May 26, 2003 The authors acknowledge the valuable hints of the anonymous referees.     

A Constructive Finite Field Method for Scattering Points on the Surface of <Emphasis Type="Italic">d</Emphasis>-Dimensional Spheres

d +1 variables over finite fields to scatter points on the surface of the unit sphere S ^d , d≥1. Applications are given for spherical t designs and generalized s energies. Received May 2, 2001; revised October 2, 2001 Published online February 18, 2002     

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     

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     

Data Mining with Sparse Grids

O (h _n ⁻¹ n ^{d −1}) instead of O(h _n ^−d ) grid points and unknowns are involved. Here d denotes the dimension of the feature space and h _n = 2 ⁻ⁿ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique [42] where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination. In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e. the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods. Received April 25, 2001     

Uniform Pointwise Convergence of Finite Difference Schemes Using Grid Equidistribution

A singularly perturbed quasilinear two-point boundary value problem is considered. The problem is discretized using a simple upwind finite difference scheme on adapted meshes using grid equidistribution of monitor functions. We derive sufficient conditions on the monitor function that guarantee uniform convergence in the discrete maximum norm no matter how small the perturbation parameter is. These results can be used to deduce uniform convergence of the scheme for a number of layer-adapted meshes. We also propose an adaptive procedure for the numerical treatment of the boundary value problem. Numerical experiments for the schemes are presented. Received November 12, 1999; revised April 20, 2000     

Spectral Galerkin Discretization for Hydrodynamic Stability Problems

A spectral Galerkin discretization for calculating the eigenvalues of the Orr-Sommerfeld equation is presented. The matrices of the resulting generalized eigenvalue problem are sparse. A convergence analysis of the method is presented which indicates that a) no spurious eigenvalues occur and b) reliable results can only be expected under the assumption of scale resolution, i.e., that Re/p ² is small; here Re is the Reynolds number and p is the spectral order. Numerical experiments support that the assumption of scale resolution is necessary in order to obtain reliable results. Exponential convergence of the method is shown theoretically and observed numerically. Received November 11, 1998; revised March 1, 2000     

A Note on Transformed Density Rejection

In this paper we describe a version of transformed density rejection that requires less uniform random numbers. Random variates below the squeeze are generated by inversion. For the expensive part between squeeze and density an algorithm that uses a covering with triangles is introduced. Received August 23, 1999; revised March 6, 2000     

Iterative Stokes Solvers in the Harmonic Velte Subspace

We explore the prospects of utilizing the decomposition of the function space (H ¹ ₀) ⁿ (where n=2,3) into three orthogonal subspaces (as introduced by Velte) for the iterative solution of the Stokes problem. It is shown that Uzawa and Arrow-Hurwitz iterations – after at most two initial steps – can proceed fully in the third, smallest subspace. For both methods, we also compute optimal iteration parameters. Here, for two-dimensional problems, the lower estimate of the inf-sup constant by Horgan and Payne proves useful and provides an inclusion of the spectrum of the Schur complement operator of the Stokes problem. We further consider the conjugate gradient method in the third Velte subspace and derive a corresponding convergence estimate. Computational results show the effectiveness of this approach for discretizations which admit a discrete Velte decomposition. Received June 11, 1999; revised October 27, 2000     

Iterative Methods for Linear Complementarity Problems with Interval Data

A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x ^*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x ^*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions on the starting vector deliver nested sequences converging to [x ^*]. We close our paper with some examples which illustrate our theoretical results. Received October 7, 2002; revised April 15, 2003 Published online: June 23, 2003 RID="*" ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday. We are grateful to the referee who has given a series of valuable comments.     

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     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 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     

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     

Smolyak's Construction of Cubature Formulas of Arbitrary Trigonometric Degree

We study cubature formulas for d-dimensional integrals with a high trigonometric degree. To obtain a trigonometric degree in dimension d, we need about function values if d is large. Only a small number of arithmetical operations is needed to construct the cubature formulas using Smolyak's technique. We also compare different methods to obtain formulas with high trigonometric degree. Received: April 8, 1998     

Uniformly Effective Numerical Methods for Hyperbolic Systems

A unified method to compute compressible and incompressible flows is presented. Accuracy and efficiency do not degrade as the Mach number tends to zero. A staggered scheme solved with a pressure correction method is used. The equation of state is arbitrary. A Riemann problem for the barotropic Euler equations with nonconvex equation of state is solved exactly and numericaly. A hydrodynamic flow with cavitation in which the Mach number varies between 10⁻³ and 20 is computed. Unified methods for compressible and incompressible flows are further discussed for the flow of a perfect gas. The staggered scheme with pressure correction is found to have Mach-uniform accuracy and efficiency, and for the fully compressible case the accuracy is comparable with that of established schemes for compressible flows. Received October 20, 1999; revised May 26, 2000     

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 New Multisection Technique in Interval Methods for Global Optimization

A new multisection technique in interval methods for global optimization is investigated, and numerical tests demonstrate that the efficiency of the underlying global optimization method can be improved substantially. The heuristic rule is based on experiences that suggest the subdivision of the current subinterval into a larger number of pieces only if it is located in the neighbourhood of a minimizer point. An estimator of the proximity of a subinterval to the region of attraction to a minimizer point is utilized. According to the numerical study made, the new multisection strategies seem to be indispensable, and can improve both the computational and the memory complexity substantially. Received May 31, 1999; revised January 20, 2000     

A Dynamic Self-Stabilizing Algorithm for Constructing a Transport Net

transport net corresponding to an undirected biconnected graph on a distributed or network model of computation. The algorithm is resilient to transient faults and does not require initialization. In addition, it is capable of handling topology changes in a transient manner. The paper includes a correctness proof of the algorithm. Finally, it concludes with some final remarks. Received November 26, 2001 Published online February 18, 2002