Look-ahead in Bi-CGSTAB and other product methods for linear systems

The Lanczos method for solvingAx = b consists in constructing the sequence of vectorsx _k such thatr _k =b – Ax _k =P _k (A)r ₀ whereP _k is the orthogonal polynomial of degree at mostk with respect to the linear functionalc whose moments arec( _i ) =c _i = (y, A ⁱ r ₀).In this paper we discuss how to avoid breakdown and near-breakdown in a whole class of methods defined byr _k =Q _k (A)P _k (A)r ₀,Q _k being a given polynomial. In particular, the case of the Bi-CGSTAB algorithm is treated in detail. Some other choices of the polynomialsQ _k are also studied.     

ABS methods and ABSPACK for linear systems and optimization: A review

ABS methods are a large class of methods, based upon the Egervary rank reducing algebraic process, first introduced in 1984 by Abaffy, Broyden and Spedicato for solving linear algebraic systems, and later extended to nonlinear algebraic equations, to optimization problems and other fields; software based upon ABS methods is now under development. Current ABS literature consists of about 400 papers. ABS methods provide a unification of several classes of classical algorithms and more efficient new solvers for a number of problems. In this paper we review ABS methods for linear systems and optimization, from both the point of view of theory and the numerical performance of ABSPACK.Work partially supported by ex MURST 60% 2001 funds.E. Spedicato     

On modification of certain methods of the conjugate direction type for solving systems of linear algebraic equations

A modification of certain well-known methods of the conjugate direction type is proposed and examined. The modified methods are more stable with respect to the accumulation of round-off errors. Moreover, these methods are applicable for solving ill-conditioned systems of linear algebraic equations that, in particular, arise as approximations of ill-posed problems. Numerical results illustrating the advantages of the proposed modification are presented.     

On modification of certain methods of the conjugate direction type for solving rectangular systems of linear algebraic equations

The use of modifications of certain well-known methods of the conjugate direction type for solving systems of linear algebraic equations with rectangular matrices is examined. The modified methods are shown to be superior to the original versions with respect to the round-off accumulation; the advantage is especially large for ill-conditioned matrices. Examples are given of the efficient use of the modified methods for solving certain fairly large ill-conditioned problems.     

A class of direct methods for linear systems

Summary A class of methods of direct type for solving determined or underdetermined, full rank or deficient rank linear systems is presented and theoretically analyzed. The class can be considered as a generalization of the methods of Brent and Brown as restricted to linear systems and implicitly contains orthogonal,LU andLL ^T factorization methods.     

Conjugate residual methods for almost symmetric linear systems

This paper concerns the use of conjugate residual methods for the solution of nonsymmetric linear systems arising in applications to differential equations. We focus on an application derived from a seismic inverse problem. The linear system is a small perturbation to a symmetric positive-definite system, the nonsymmetries arising from discretization errors in the solution of certain boundary-value problems. We state and prove a new error bound for a class of generalized conjugate residual methods; we show that, in some cases, the perturbed symmetric problem can be solved with an error bound similar to the one for the conjugate residual method applied to the symmetric problem. We also discuss several applications for special distributions of eigenvalues.This work was supported in part by the National Science Foundation, Grants DMS-84-03148 and DCR-81-16779, and by the Office of Naval Research, Contract N00014-85-K-0725.     

Numerical experiments with ABS algorithms for linear systems on a parallel machine

Numerical results are obtained on sequential and parallel versions of ABS algorithms for linear systems for both full matrices andq-band matrices. The results using the sequential algorithm on full matrices indicate the superiority of a particular implementation of the symmetric algorithm. The condensed form of the algorithm is well suited for implementation in a parallel environment, and results obtained on the IBM 4381 system favor a synchronous implementation over the asynchronous one. Results are obtained from sequential implementations of theLU, Cholesky, and symmetric algorithms of the ABS class forq-band matrices able to reduce memory storage. A simple parallelization of do-loops for calculating components gives interesting performances.This work has been developed in the framework of a collaboration between IBM-ECSEC, Rome, Italy, and the Department of Mathematics of the University of Bergamo, Bergamo, Italy.The author is grateful to Prof. J. Abaffy (University of Economics, Budapest), Prof. L. Dixon (Hatfield Polytechnic), and Prof. E. Spedicato (Department of Mathematics, University of Bergamo) for useful suggestions.     

Superlinear convergence theorems for Newton-type methods for nonlinear systems of equations

In this paper, someQ-order convergence theorems are given for the problem of solving nonlinear systems of equations when using very general finitely terminating methods for the solution of the associated linear systems. The theorems differ from those of Dembo, Eisenstat, and Steihaug in the different stopping condition and in their applicability to the nonlinear ABS algorithm.Lecture presented at the University of Bergamo, Bergamo, Italy, October 1989.     

Stability of linear systems with time-varying delays: A direct frequency domain approach

The stability of linear systems with uncertain bounded time-varying delays (without any constraints on the delay derivatives) is analyzed. It is assumed that the system is stable for some known constant values of the delays (but may be unstable for zero delay values). The existing (Lyapunov-based) stability methods are restricted to the case of a single non-zero constant delay value, and lead to complicated and restrictive results. In the present note for the first time a stability criterion is derived in the general multiple delay case without any constraints on the delay derivative. The simple sufficient stability condition is given in terms of the system matrices and the lengths of the delay segments. Different from the existing frequency domain methods which usually apply the small gain theorem, the suggested approach is based on the direct application of the Laplace transform to the transformed system and on the bounding technique in _L2$L_2$. A numerical example illustrates the efficiency of the method.     

Superlinear convergence theorem in the ABSg class of algorithms for nonlinear algebraic equations

In this paper, it is shown that, when two subclasses of algorithms in the ABSg family are applied to a set of nonlinear algebraic equations, then the convergence is superlinear. The conditions for the theorem to be true are essentially the same as those that apply to the Newton method.This work was undertaken while the author was at Hatfield Polytechnic working under SERC Grant No. GR/E 07760.     

Deflated Krylov subspace methods for nearly singular linear systems

This paper concerns the use of Krylov subspace methods for the solution of nearly singular nonsymmetric linear systems. We show that the incomplete orthogonalization methods (IOM) in conjunction with certain deflation techniques of Stewart, Chan, and Saad can be used to solve large nonsymmetric linear systems which are nearly singular.This work was supported by the National Science Foundation, Grants DMS-8403148 and DCR-81-16779, and by the Office of Naval Research, Contract N00014-85-K-0725.     

Global convergence of the affine scaling methods for degenerate linear programming problems

In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.This paper was presented at the International Symposium Interior Point Methods for Linear Programming: Theory and Practice, held on January 18–19, 1990, at the Europa Hotel, Scheveningen, the Netherlands.     

A class of methods for linear programming

A class of methods is presented for solving standard linear programming problems. Like the simplex method, these methods move from one feasible solution to another at each iteration, improving the objective function as they go. Each such feasible solution is also associated with a basis. However, this feasible solution need not be an extreme point and the basic solution corresponding to the associated basis need not be feasible. Nevertheless, an optimal solution, if one exists, is found in a finite number of iterations (under nondegeneracy). An important example of a method in the class is the reduced gradient method with a slight modification regarding selection of the entering variable.     

Projected equation methods for approximate solution of large linear systems

We consider linear systems of equations and solution approximations derived by projection on a low-dimensional subspace. We propose stochastic iterative algorithms, based on simulation, which converge to the approximate solution and are suitable for very large-dimensional problems. The algorithms are extensions of recent approximate dynamic programming methods, known as temporal difference methods, which solve a projected form of Bellman’s equation by using simulation-based approximations to this equation, or by using a projected value iteration method.     

A conjugate gradient algorithm for sparse linear inequalities

This paper presents a conjugate gradient method for solving systems of linear inequalities. The method is of dual optimization type and consists of two phases which can be implemented in a common framework. Phase 1 either finds the minimum-norm solution of the system or detects the inconsistency of the system. In the latter event, the method proceeds to Phase 2 in which an approximate least-squares solution to the system is obtained. The method is particularly suitable to large scale problems because it preserves the sparsity structure of the problem. Its efficiency is shown by computational comparisons with an SOR type method.     

Branch-and-bound methods for solving systems of Lipschitzian equations and inequalities

In this note, we show how branch-and-bound methods previously proposed for solving broad classes of multiextremal global optimization problems can be applied for solving systems of Lipschitzian equations and inequalities over feasible sets defined by various types of constraints. Some computational results are given.This research was accomplished while the second author was a fellow of the Alexander von Humboldt Foundation at the University of Trier, Trier, West Germany.     

Solving symmetric indefinite systems in an interior-point method for linear programming

We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite augmented systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite normal equations that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This work has been supported in part by National Science Foundation grants DDM-8908818 (Fourer) and CCR-8810107 (Mehrotra), and by a grant from GTE Laboratories (Mehrotra).     

A method for constructing solutions to linear systems of partial differential equations

We obtain some conditions of solvability in Sobolev spaces for the systems of linear partial differential equations and deduce the corresponding formulas for solutions to these systems. The solutions are given as the sum of the series whose terms are the iterations of some pseudodifferential operators constructed explicitly.     

A normalized sparse linear equations solver

Normalized factorization procedures for the solution of large sparse linear finite element systems have been recently introduced in [3]. In these procedures the large sparse symmetric coefficient matrix of irregular structure is factorized exactly to yield a normalized direct solution method. Additionally, approximate factorization procedures yield implicit iterative methods for the finite difference or finite element solution. The numerical implementation of these algorithms is presented here and FORTRAN subroutines for the efficient solution of the resulting large sparse symmetric linear systems of algebraic equations are given.     

A modification of conjugate direction methods

A modification of well-known conjugate direction methods is proposed and examined. The modified methods are more stable with respect to round-off error accumulation and are applicable to ill-conditioned and ill-posed problems. The advantages of the modification are illustrated by numerical experiments.