Minimal Expansions in Redundant Number Systems and Shortest Paths in Graphs

We consider digit expansions in redundant number systems to base q with and consider such an expansion as minimal, if is minimal. We describe an efficient algorithm for determining a minimal representation and give an explicit characterization of optimal representations for odd q. Received: July 20, 1999; revised August 23 1999     

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     

Acquisition of Complex Model Knowledge by Domain Theory-Controlled Generalization

Nearly all three-dimensional reconstruction methods lack proper model knowledge that reflects the scene. Model knowledge is required in order to reduce ambiguities which occur during the reconstruction process. It must comprise the scene and is therefore complex, and additionally difficult to acquire. In this paper we present an approach for the learning of complex model knowledge. A (large) sample set of three-dimensionally acquired buildings represented as graphs is generalized by the use of background knowledge. The background knowledge entails domain-specific knowledge and is utilized for the search guidance during the generalization process of EXRES. The generalization result is a distribution of relevant patterns which reduces ambiguities occurring in 3D object reconstruction (here: buildings). Three different applications for the 3D reconstruction of buildings from aerial images are executed whereas binary relations of so-called building atoms, namely tertiary nodes and faces, and building models are learned. These applications are evaluated based on (a) the estimated empirical generalization error and (b) the use of information coding theory and statistics by comparing the learned knowledge with non-available a priori knowledge. Received: June 3, 1998; revised November 5, 1998     

A Note on the Stability of Gauss–Jordan Elimination for Diagonally Dominant Matrices

Peters and Wilkinson [2] state that “it is well known that Gauss–Jordan is stable” for a diagonally dominant matrix, but a proof does not seem to have been published [1]. The present note fills this gap. Gauss–Jordan elimination is backward stable for matrices diagonally dominant by rows and not for those diagonally dominant by columns. In either case it is forward stable. Received February 28, 2000     

From Methods to Images

This paper presents a system for automatically selecting images in an image database to be used as illustrations of an image method or analysis process. This problem is related to the teleteaching of image processing which uses already implemented libraries of algorithms. This is in the context of a teleteaching European project. We first give a Bayesian approach to this problem, by using an image basis. Then we show how to use the Haar transform for this purpose. Finally we give examples and discuss our approach. Received: June 8, 1998; revised December 17, 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     

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     

Analysis of Some Elementary Algorithms for Prime Factorization

For factoring a positive integer n into primes, four variants of the elementary algorithm are analysed. The worst-case time complexities vary from Θ() up to Θ(). The average time complexities vary from Θ() up to Θ(). Received August 21, 1998; revised September 14, 2000     

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     

An Adaptive Routing Algorithm for WK-Recursive Topologies

This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on adaptive routing, takes advantage of the geometric properties of such topologies. Once a source node S and destination node D have been determined for a message communication, they characterize, at some level l, two virtual nodes and that respectively contain S but not D and D but not S. Such virtual nodes characterize other (where is the node degree for a fixed topology) virtual nodes of the same level that contain neither S nor D. Consequently, it is possible to locate triangles whose vertices are these virtual nodes with property to share the same path, called the self-routing path, directly connecting to . When the self-routing path is unavailable to transmit a message from S to D because of deadlock, fault, and congestion conditions, the routing strategy can follow what we call the triangle rule to deliver it. The proposed communication scheme has the advantage that 1) it is the same for all three conditions; 2) each node of a WK-recursive network, to transmit messages, does not require any information about their presence or location. Furthermore, this routing algorithm is able to tolerate up to faulty links. Received: July 19, 1998; revised May 17, 1999     

On the Attainable Order of Collocation Methods for the Neutral Functional-Differential Equations with Proportional Delays

In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫₀ ^t by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE): and the delay Volterra integro-differential equation (DVIDE) : with proportional delays p _i t and q _i t, 0<p _i ,q _i ≤1 and complex numbers a,b _i and c _i . We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u _it (t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M _m (t) of v(th) or M^ _m (t) of u _it (th), t∈[0,1] such that the rational approximant v(h) or u _it (h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h ^{2 m +1}). If they exist, then we actually give the conditions of M _m (t) and M^ _m (t), respectively. Received September 17, 1998; revised September 30, 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     

The K r -Packing Problem

For a fixed integer r≥2, the K _r -packing problem is to find the maximum number of pairwise vertex-disjointK _r 's (complete graphs on r vertices) in a given graph. The K _r -factor problem asks for the existence of a partition of the vertex set of a graph into K _r 's. The K _r -packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r≥3 – it is known that for r≥3 the K _r -factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the K _r -packing problem on restricted classes of graphs. We first prove that for r≥3 the K _r -packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K ₃-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K ₃-packing and the K _r -factor problems on split graphs (this is interesting in light of the fact that K _r -packing becomes NP-complete on split graphs for r≥4), and for the K _r -packing problem on cographs. Received September 27, 1999; revised August 14, 2000     

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     

Direct Integration of the Newton Potential over Cubes

In boundary element methods, the evaluation of the weakly singular integrals can be performed either a) numerically, b) symbolically, i.e., by explicit expressions, or c) in a combined manner. The explicit integration is of particular interest, when the integrals contain the singularity or if the singularity is rather close to the integration domain. In this paper we describe the explicit expressions for the sixfold volume integrals arising for the Newton potential, i.e., for a 1/r integrand. The volume elements are axi-parallel bricks. The sixfold integrals are typical for the Galerkin method. However, the threefold integral arising from collocation methods can be derived in the same way. Received April 18, 2001; revised September 17, 2001 Published online April 25, 2002     

A Multigrid Approach for Minimizing a Nonlinear Functional for Digital Image Matching

In this paper, we consider a multigrid application in digital image processing. Here, the problem is to find a map, which transforms an image T into another image R such that the grey level of the different images are nearly equal in every picture-element. This problem arises in the investigation of human brains. The complete inverse problem is ill posed in the sense of Hadamard and nonlinear, so the numerical solution is quite difficult. We solve the inverse problem by a Landweber iteration. In each minimization step an approximate solution for the linearized problem is computed with a multigrid method as an inner iteration. Finally, we present some experimental results for synthetic and real images. Received December 30, 1998; revised August 16, 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 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     

Cache-Aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions

Conventional implementations of iterative numerical algorithms, especially multigrid methods, merely reach a disappointing small percentage of the theoretically available CPU performance when applied to representative large problems. One of the most important reasons for this phenomenon is that the need for data locality due to poor main memory latency and limited bandwidth is entirely neglected by many developers designing numerical software. Only when most of the data to be accessed during the computation are found in the system cache (or in one of the caches if the machine architecture comprises a cache hierarchy) fast program execution can be expected. Otherwise, i.e. in case of a significant rate of cache misses, the processor must stay idle until the necessary operands are fetched from main memory, whose cycle time is in general extremely large compared to the time needed to execute a floating point instruction. In this paper, we describe program transformation techniques developed to improve the cache performance of two-dimensional multigrid algorithms. Although we merely consider the solution of Poisson's equation on the unit square using structured grids, our techniques provide valuable hints towards the efficient treatment of more general problems. Received January 31, 1999; revised October 17, 1999     

Risk Theory with a nonlinear Dividend Barrier

In the framework of classical risk theory we investigate a surplus process in the presence of a nonlinear dividend barrier and derive equations for two characteristics of such a process, the probability of survival and the expected sum of discounted dividend payments. Number-theoretic solution techniques are developed for approximating these quantities and numerical illustrations are given for exponential claim sizes and a parabolic dividend barrier. Received May 8, 2001 Published online: July 8, 2002