Imperfect conjugate gradient algorithms for extended quadratic functions

Summary Generalized conjugate gradient algorithms which are invariant to a nonlinear scaling of a strictly convex quadratic function are described. The algorithms when applied to scaled quadratic functionsfR _n R ₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹(R ₁) an arbitrary strictly monotone functionh generate the same direction vectors as for the functionF without perfect steps.     

Parallel and superfast algorithms for Hankel systems of equations

Summary Utilizing kernel structure properties a unified construction of Hankel matrix inversion algorithms is presented. Three types of algorithms are obtained: 1)O(n ²) complexity Levinson type, 2)O (n) parallel complexity Schur-type, and 3)O(n log² n) complexity asymptotically fast ones. All algorithms work without additional assumption (like strong nonsingularity).     

Convergence of the multilevel Full Approximation Scheme including theV-cycle

Summary The multilevel Full Approximation Scheme (FAS ML) is a well-known solver for nonlinear boundary value problems. In this paper we prove local quantitative convergence statements for a class of FAS ML algorithms in a general Hilbertspace setting. This setting clearly exhibits the structure of FAS ML. We prove local convergence of a nested iteration for a rather concrete class of FAS ML algorithms in whichV-cycles and only one Jacobilike pre- and post-smoothing on each level are used.     

Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix

Summary. In this paper we propose four algorithms to compute truncated pivoted QR approximations to a sparse matrix. Three are based on the Gram–Schmidt algorithm and the other on Householder triangularization. All four algorithms leave the original matrix unchanged, and the only additional storage requirements are arrays to contain the factorization itself. Thus, the algorithms are particularly suited to determining low-rank approximations to a sparse matrix. Received February 23, 1998 / Revised version received April 16, 1998     

The convergence of two numerical schemes for the Navier-Stokes equations

Summary This paper deals with some convergence/stability results concerning two numerical methods for solving the incompressible nonstationary Navier-Stokes equations. The algorithms are of a particular kind in what regards time discretization (more precisely, of the Peaceman-Rachford and the Strang type resp.), and have been obtained by modifying slightly the numerical treatment of the nonlinear terms in other schemes due to Glowinski et al. (1980). We first describe the full discretization of the homogeneous Dirichlet problem using a (general) external approximation of the spatial functional spaces involved (a particular and simple choice of such an approximation is the standardP ₂-Lagrange finite element for the velocity field when the fluid is bidimensional). Then we establish and prove convergence and stability and make some comments on the numerical treatment of other (generally nonhomogeneous) boundary conditions. The theoretical results show that the schemes are (at least) conditionally stable and convergent, which justifies the success of Glowinski's methods.     

Parallel algorithms for analyzing activity networks

Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms haveO(logn) time complexity and the remaining one achievesO(logd log logn) time bound, whered is the diameter of the digraph representing the activity network withn nodes. All these algorithms work on a CRCW PRAM and requireO(n ³) processors.     

Algorithmes mixtes asynchrones. Etude de convergence monotone

Summary In this paper we introduce two classes of iterative algorithms which we call Asynchronous mixed algorithms and we study their convergence under partial ordering. These algorithms can be implemented just as well on monoprocessors as on multiprocessors, and, along with their convergence study, constitute a generalization of the mixed classical Newton-relaxation algorithms.

---

Résumé Nous introduisons dans cet article deux classes d'algorithmes itératifs que nous appelons «Algorithmes mixtes asynchrones» et nous en étudierons la convergence selon un ordre partiel. Ces algorithmes sont implémentables aussi bien sur les monoprocesseurs que sur les multiprocesseurs, et avec leur étude de convergence constituent une généralisation des algorithmes mixtes classiques «Newton-relaxation».

     

Estimates for multigrid methods based on red-black Gauss-Seidel smoothings

Summary TheMGR[v] algorithms of Ries, Trottenberg and Winter, the Algorithms 2.1 and 6.1 of Braess and the Algorithm 4.1 of Verfürth are all multigrid algorithms for the solution of the discrete Poisson equation (with Dirichlet boundary conditions) based on red-black Gauss-Seidel smoothing. Both Braess and Verfürth give explicit numerical upper bounds on the rate of convergence of their methods in convex polygonal domains. In this work we reconsider these problems and obtain improved estimates for theh–2h Algorithm 4.1 as well asW-cycle estimates for both schemes in non-convex polygonal domains. The proofs do not depend on the strengthened Cauchy inequality.Sponsored by the Air Force Office of Scientific Research under Contract No. AFOSR-86-0163     

On neighbouring matrices with quadratic elementary divisors

Summary Algorithms are presented which compute theQR factorization of an order-n Toeplitz matrix inO(n ²) operations. The first algorithm computes onlyR explicitly, and the second computes bothQ andR. The algorithms are derived from a well-known procedure for performing the rank-1 update ofQR factors, using the shift-invariance property of the Toeplitz matrix. The algorithms can be used to solve the Toeplitz least-squares problem, and can be modified to solve Toeplitz systems inO(n) space.     

Global approximate Newton methods

Summary We derive a class of globally and quadratically converging algorithms for a system of nonlinear equations,g(u)=0, whereg is a sufficiently smooth homeomorphism. Particular attention is directed to key parameters which control the iteration. Several examples are given that have been successful in solving the coupled nonlinear PDEs which arise in semiconductor device modelling.     

Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems

Summary A forward error analysis is presented for the Björck-Pereyra algorithms used for solving Vandermonde systems of equations. This analysis applies to the case where the points defining the Vandermonde matrix are nonnegative and are arranged in increasing order. It is shown that for a particular class of Vandermonde problems the error bound obtained depends on the dimensionn and on the machine precision only, being independent of the condition number of the coefficient matrix. By comparing appropriate condition numbers for the Vandermonde problem with the forward error bounds it is shown that the Björck-Pereyra algorithms introduce no more uncertainty into the numerical solution than is caused simply by storing the right-hand side vector on the computer. A technique for computing running a posteriori error bounds is derived. Several numerical experiments are presented, and it is observed that the ordering of the points can greatly affect the solution accuracy.     

Generalized multiresolution analysis on unstructured grids

Summary. Efficiency of high-order essentially non-oscillatory (ENO) approximations of conservation laws can be drastically improved if ideas of multiresolution analysis are taken into account. These methods of data compression not only reduce the necessary amount of discrete data but can also serve as tools in detecting local low-dimensional features in the numerical solution. We describe the mathematical background of the generalized multiresolution analysis as developed by Abgrall and Harten in [14], [15] and [3]. We were able to ultimately reduce the functional analytic background to matrix-vector operations of linear algebra. We consider the example of interpolation on the line as well as the important case of multiresolution analysis of cell average data which is used in finite volume approximations. In contrast to Abgrall and Harten, we develop a robust agglomeration procedure and recovery algorithms based on least-squeare polynomials. The efficiency of our algorithms is documented by means of several examples. Received April 4, 1998 / Revised version August 2, 1999 / Published online June 8, 2000     

A continued fraction algorithm

Summary Two existing algorithms for the evaluation of a finite sequence of convergents of a continued fraction are considered. Each method has a drawback concerning numerical stability or computational effort. A third algorithm is presented which requires less computations than the first method, and generally is more stable than the second one. The results are illustrated by numerical examples. The connection with Mikloko's algorithm is shown.     

Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems

Numerical algorithms with complexityO(n ²) operations are proposed for solving matrix Nehari and Nehari-Takagi problems withn interpolation points. The algorithms are based on explicit formulas for the solutions and on theorems about cascade decomposition of rational matrix function given in a state space form. The method suggests also fast algorithms for LDU factorizations of structured matrices. The numerical behavior of the designed algorithms is studied for a wide set of examples.     

Reguläre Zerlegungen und Berechnung des Spektralradius nichtnegativer Matrizen

Summary On the basis of a Rayleigh Quotient Iteration method in [10] and a Maximal Quotient Iteration method in [5, 8] two algorithms for solving special eigenvalue problems are developed. The characteristic properties of these methods lie in the application of iterative linear methods to solving systems of linear equations. The convergence properties are investigated. We apply the algorithms to the computation of the spectralradius of a nonnegative irreducible matrix.

     

Fast verification of solutions of matrix equations

Summary. In this paper, we are concerned with a matrix equation where A is an real matrix and x and b are n-vectors. Assume that an approximate solution is given together with an approximate LU decomposition. We will present fast algorithms for proving nonsingularity of A and for calculating rigorous error bounds for . The emphasis is on rigour of the bounds. The purpose of this paper is to propose different algorithms, the fastest with flops computational cost for the verification step, the same as for the LU decomposition. The presented algorithms exclusively use library routines for LU decomposition and for all other matrix and vector operations. Received June 16, 1999 / Revised version received January 25, 2001 / Published online June 20, 2001     

Fast inversion algorithms of Toeplitz-plus-Hankel matrices

Summary The paper deals with the problems of fast inversion of matricesA=T+H, whereT is Toeplitz andH is Hankel. Several algorithms are presented and compared, among them algorithms working for arbitrary strongly nonsingular matricesA=T+H.     

New look-ahead Lanczos-type algorithms for linear systems

Summary. A breakdown (due to a division by zero) can arise in the algorithms for implementing Lanczos' method because of the non-existence of some formal orthogonal polynomials or because the recurrence relationship used is not appropriate. Such a breakdown can be avoided by jumping over the polynomials involved. This strategy was already used in some algorithms such as the MRZ and its variants. In this paper, we propose new implementations of the recurrence relations of these algorithms which only need the storage of a fixed number of vectors, independent of the length of the jump. These new algorithms are based on Horner's rule and on a different way for computing the coefficients of the recurrence relationships. Moreover, these new algorithms seem to be more stable than the old ones and they provide better numerical results. Numerical examples and comparisons with other algorithms will be given. Received September 2, 1997 / Revised version received July 24, 1998