Numerical solution of constant coefficient linear delay differential equations as abstract Cauchy problems

Summary. In this paper we present an approach for the numerical solution of delay differential equations where , and , different from the classical step-by-step method. We restate (1) as an abstract Cauchy problem and then we discretize it in a system of ordinary differential equations. The scheme of discretization is proved to be convergent. Moreover the asymptotic stability is investigated for two significant classes of asymptotically stable problems (1). Received May 4, 1998 / Revised version received January 25, 1999 / Published online November 17, 1999     

Numerical solution of a secular equation

Summary. A method is proposed for the solution of a secular equation, arising in modified symmetric eigenvalue problems and in several other areas. This equation has singularities which make the application of standard root-finding methods difficult. In order to solve the equation, a class of transformations of variables is considered, which transform the equation into one for which Newton's method converges from any point in a certain given interval. In addition, the form of the transformed equation suggests a convergence accelerating modification of Newton's method. The same ideas are applied to the secant method and numerical results are presented. Received July 1, 1994     

Improved smoothing-type methods for the solution of linear programs

Summary. We consider a smoothing-type method for the solution of linear programs. Its main idea is to reformulate the primal-dual optimality conditions as a nonlinear and nonsmooth system of equations, and to apply a Newton-type method to a smooth approximation of this nonsmooth system. The method presented here is a predictor-corrector method, and is closely related to some methods recently proposed by Burke and Xu on the one hand, and by the authors on the other hand. However, here we state stronger global and/or local convergence properties. Moreover, we present quite promising numerical results for the whole netlib test problem collection. Received August 9, 2000 / Revised version received September 28, 2000 / Published online June 7, 2001     

Computation of orthonormal factors for fundamental solution matrices

Summary. In this work, we introduce and analyze two new techniques for obtaining the Q factor in the QR factorization of some (or all) columns of a fundamental solution matrix Y of a linear differential system. These techniques are based on elementary Householder and Givens transformations. We implement and compare these new techniques with existing approaches on some examples. Received October 27, 1997 / Revised version received September 21, 1998 / Published online August 19, 1999     

Ruled Weingarten surfaces in Minkowski 3-space

We characterize all ruled surfaces in Minkowski 3-space with a relation between the Gauss and mean curvature (Weingarten surfaces). It turns out that, except if the rulings are in a null direction, these are given by Lorentzian screw motions of straight lines. However, if the rulings are always in a null direction, then every ruled surface is Weingarten. Received: 9 February 1998 / Revised version: 20 December 1998     

Absorbing boundary conditions for diffusion equations

Summary. We construct and analyse a family of absorbing boundary conditions for diffusion equations with variable coefficients, curved artifical boundary, and arbitrary convection. It relies on the geometric identification of the Dirichlet to Neumann map and rational interpolation of in the complex plane. The boundary conditions are stable, accurate, and practical for computations. Received December 12, 1992 / Revised version received July 4, 1994     

Embedded constant mean curvature surfaces with special symmetry

We give sharp, necessary conditions on complete embedded CMC surfaces with three ends and an extra reflection symmetry. The respective submoduli space is a two-dimensional variety in the moduli space of general CMC surfaces. Fundamental domains of our CMC surfaces are characterized by associated great circle polygons in the three-sphere. Received: 23 January 1998 / Revised version: 23 October 1998     

Minimal surfaces: a geometric three dimensional segmentation approach

Summary. A novel geometric approach for three dimensional object segmentation is presented. The scheme is based on geometric deformable surfaces moving towards the objects to be detected. We show that this model is related to the computation of surfaces of minimal area (local minimal surfaces). The space where these surfaces are computed is induced from the three dimensional image in which the objects are to be detected. The general approach also shows the relation between classical deformable surfaces obtained via energy minimization and geometric ones derived from curvature flows in the surface evolution framework. The scheme is stable, robust, and automatically handles changes in the surface topology during the deformation. Results related to existence, uniqueness, stability, and correctness of the solution to this geometric deformable model are presented as well. Based on an efficient numerical algorithm for surface evolution, we present a number of examples of object detection in real and synthetic images. Received January 4, 1996 / Revised version received August 2, 1996     

Numerical solution by LMMs of stiff delay differential systems modelling an immune response

Summary. We consider the application of linear multistep methods (LMMs) for the numerical solution of initial value problem for stiff delay differential equations (DDEs) with several constant delays, which are used in mathematical modelling of immune response. For the approximation of delayed variables the Nordsieck's interpolation technique, providing an interpolation procedure consistent with the underlying linear multistep formula, is used. An analysis of the convergence for a variable-stepsize and structure of the asymptotic expansion of global error for a fixed-stepsize is presented. Some absolute stability characteristics of the method are examined. Implementation details of the code DIFSUB-DDE, being a modification of the Gear's DIFSUB, are given. Finally, an efficiency of the code developed for solution of stiff DDEs over a wide range of tolerances is illustrated on biomedical application model. Received March 23, 1994 / Revised version received March 13, 1995     

Reliable parallel solution of bidiagonal systems

Summary. This paper presents a new efficient algorithm for solving bidiagonal systems of linear equations on massively parallel machines. We use a divide and conquer approach to compute a representative subset of the solution components after which we solve the complete system in parallel with no communication overhead. We address the numerical properties of the algorithm in two ways: we show how to verify the à posteriori backward stability at virtually no additional cost, and prove that the algorithm is à priori forward stable. We then show how we can use the algorithm in order to bound the possible perturbations in the solution components. Received March 13, 1998 / Revised version received December 21, 1999 / Published online June 20, 2001     

A polynomial of graphs on surfaces

ribbon graphs , i.e., graphs realized as disks (vertices) joined together by strips (edges) glued to their boundaries, corresponding to neighbourhoods of graphs embedded into surfaces. We construct a four-variable polynomial invariant of these objects, the ribbon graph polynomial, which has all the main properties of the Tutte polynomial. Although the ribbon graph polynomial extends the Tutte polynomial, its definition is very different, and it depends on the topological structure in an essential way. Received: 14 September 2000 / Published online: 18 January 2002     

Preserving monotonicity in the numerical solution of Riccati differential equations

Summary. Solutions of symmetric Riccati differential equations (RDEs for short) are in the usual applications positive semidefinite matrices. Moreover, in the class of semidefinite matrices, solutions of different RDEs are also monotone, with respect to properly ordered data. Positivity and monotonicity are essential properties of RDEs. In Dieci and Eirola (1994), we showed that, generally, a direct discretization of the RDE cannot maintain positivity, and be of order greater than one. To get higher order, and to maintain positivity, we are thus forced to look into indirect solution procedures. Here, we consider the problem of how to maintain monotonicity in the numerical solutions of RDEs. Naturally, to obtain order greater than one, we are again forced to look into indirect solution procedures. Still, the restrictions imposed by monotonicity are more stringent that those of positivity, and not all of the successful indirect solution procedures of Dieci and Eirola (1994) maintain monotonicity. We prove that by using symplectic Runge-Kutta (RK) schemes with positive weights (e.g., Gauss schemes) on the underlying Hamiltonian matrix, we eventually maintain monotonicity in the computed solutions of RDEs. Received May 2, 1995     

Block LU factorizations of M–matrices

Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular M–matrix can have when L and U are M–matrices. Received November 21, 1994 / Revised version received August 4, 1997     

Flat surfaces in the hyperbolic 3-space

In this paper we give a conformal representation of flat surfaces in the hyperbolic 3-space using the complex structure induced by its second fundamental form. We also study some examples and the behaviour at infinity of complete flat ends. Received: 18 September 1997     

Rigorous computational shadowing of orbits of ordinary differential equations

Summary. The existence of a true orbit near a numerically computed approximate orbit -- shadowing -- of autonomous system of ordinary differential equations is investigated. A general shadowing theorem for finite time, which guarantees the existence of shadowing in ordinary differential equations and provides error bounds for the distance between the true and the approximate orbit in terms of computable quantities, is proved. The practical use and the effectiveness of this theorem is demonstrated in the numerical computations of chaotic orbits of the Lorenz equations. Received December 15, 1993     

Spaces of distributions, interpolation by translates of a basis function and error estimates

Summary. Interpolation with translates of a basis function is a common process in approximation theory. The most elementary form of the interpolant consists of a linear combination of all translates by interpolation points of a single basis function. Frequently, low degree polynomials are added to the interpolant. One of the significant features of this type of interpolant is that it is often the solution of a variational problem. In this paper we concentrate on developing a wide variety of spaces for which a variational theory is available. For each of these spaces, we show that there is a natural choice of basis function. We also show how the theory leads to efficient ways of calculating the interpolant and to new error estimates. Received December 10, 1996 / Revised version received August 29, 1997     

On the convergence of multipoint iterations

Summary. This note gives a new convergence proof for iterations based on multipoint formulas. It rests on the very general assumption that if the desired fixed point appears as an argument in the formula then the formula returns the fixed point. Received March 24, 1993 / Revised version received January 1994     

Integration methods based on canonical coordinates of the second kind

Summary.   We present a new class of integration methods for differential equations on manifolds, in the framework of Lie group actions. Canonical coordinates of the second kind is used for representing the Lie group locally by means of its corresponding Lie algebra. The coordinate map itself can, in many cases, be computed inexpensively, but the approach also involves the inversion of its differential, a task that can be challenging. To succeed, it is necessary to consider carefully how to choose a basis for the Lie algebra, and the ordering of the basis is important as well. For semisimple Lie algebras, one may take advantage of the root space decomposition to provide a basis with desirable properties. The problem of ordering leads us to introduce the concept of an admissible ordered basis (AOB). The existence of an AOB is established for some of the most important Lie algebras. The computational cost analysis shows that the approach may lead to more efficient solvers for ODEs on manifolds than those based on canonical coordinates of the first kind presented by Munthe-Kaas. Numerical experiments verify the derived properties of the new methods. Received April 2, 1999 / Revised version received January 18, 2000 / Published online August 2, 2000