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     

Computation of periodic solutions in maximal monotone dynamical systems with guaranteed consistency

In this paper, we study a class of set-valued dynamical systems that satisfy maximal monotonicity properties. This class includes linear relay systems, linear complementarity systems, and linear mechanical systems with dry friction under some conditions. We discuss two numerical schemes based on time-stepping methods for the computation of the periodic solutions when these systems are periodically excited. We provide formal mathematical justifications for the numerical schemes in the sense of consistency, which means that the continuous-time interpolations of the numerical solutions converge to the continuous-time periodic solution when the discretization step vanishes. The two time-stepping methods are applied for the computation of the periodic solution exhibited by a power electronic converter and the corresponding methods are compared in terms of approximation accuracy and computation time.     

求解变延迟微分方程的一类线性多步方法的收缩性

This paper presents a sufficient condition on the contractivity of theoretical solution for a class of nonlinear systems of delay differential equations with many variable delays(MDDEs), which is weak,compared with the sufficient condition of previous articles.In addition,it discusses the numerical stability properties of a class of special linear nmltistep methods for this class nonlinear problems.And it is pointed out that not only the backwm‘d Euler method but also this class of linear multistep methods are GRNm-stable if linear interpolation is used.     

The generalized residual cutting method and its convergence characteristics

Iterative methods and especially Krylov subspace methods (KSM) are a very useful numerical tool in solving for large and sparse linear systems problems arising in science and engineering modeling. More recently, the nested loop KSM have been proposed that improve the convergence of the traditional KSM. In this article, we review the residual cutting (RC) and the generalized residual cutting (GRC) that are nested loop methods for large and sparse linear systems problems. We also show that GRC is a KSM that is equivalent to Orthomin with a variable preconditioning. We use the modified Gram–Schmidt method to derive a stable GRC algorithm. We show that GRC presents a general framework for constructing a class of “hybrid” (nested) KSM based on inner loop method selection. We conduct numerical experiments using nonsymmetric indefinite matrices from a widely used library of sparse matrices that validate the efficiency and the robustness of the proposed 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.     

求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进

分块交替分裂隐式迭代方法是求解具有鞍点结构的复线性代数方程组的一类高效迭代法.本文通过预处理技巧得到原方法的一种加速改进方法,称之为预处理分块交替分裂隐式迭代方法·理论分析给出了新方法的收敛性结果.对于一类时谐涡旋电流模型问题,我们给出了若干满足收敛条件的迭代格式.数值实验验证了新型算法是对原方法的有效改进.     

A general iterative scheme with applications to convex optimization and related fields

A general iterative scheme including relaxation and a corresponding problem class are presented. Some global convergence results are given. The acceleration of convergence is discussed, The scheme comprises a lot of known iterative methods such as subgradient methods and methods of successive orthogonal projections with relaxation. Applications to convex optimization, convex feasibility problems, systems of convex inequalities, variational inequalities, operator equations and systems of linear equations are given.     

PARALLEL ALGORITHMS OF ONE-LEG METHOD AND ITERATED DEFECT CORRECTION METHODS

The parallel algorithms of iterated defect correction methods (PIDeCM's) are constructed, which are of efficiency and high order B-convergence for general nonlinear stiff systems in ODE'S. As the basis of constructing and discussing PIDeCM's. a class of parallel one-leg methods is also investigated, which are of particular efficiency for linear systems.     

B-SERIES METHODS CANNOT BE VOLUME-PRESERVING

Volume preservation is one of the qualitative characteristics common to many dynamical systems. However, it has been proved by Kang and Shang that e.g. Runge–Kutta (RK) methods can not preserve volume for all linear source-free ODEs (let alone nonlinear ODEs). On the other hand, certain so-called Exponential Runge–Kutta (ERK) methods do preserve volume for all linear source-free ODEs. Do such ERK methods perhaps also preserve volume for all nonlinear ODEs? Here we prove that the answer to this question is negative; B-series methods (which include RK, ERK and several more classes of methods) cannot preserve volume for all source-free ODEs. The proof is presented via the theory of K-loops, which is an extension of the theory of classical rooted trees.     

Iterative Methods for a Linearly Perturbed Algebraic Matrix Riccati Equation Arising in Stochastic Control

We start with a discussion of coupled algebraic Riccati equations arising in the study of linear-quadratic optimal control problems for Markov jump linear systems. Under suitable assumptions, this system of equations has a unique positive semidefinite solution, which is the solution of practical interest. The coupled equations can be rewritten as a single linearly perturbed matrix Riccati equation with special structures. We study the linearly perturbed Riccati equation in a more general setting and obtain a class of iterative methods from different splittings of a positive operator involved in the Riccati equation. We prove some special properties of the sequences generated by these methods and determine and compare the convergence rates of these methods. Our results are then applied to the coupled Riccati equations of jump linear systems. We obtain linear convergence of the Lyapunov iteration and the modified Lyapunov iteration, and confirm that the modified Lyapunov iteration indeed has faster convergence than the original Lyapunov iteration.     

Truncated Trust Region Methods Based on Preconditioned Iterative Subalgorithms for Large Sparse Systems of Nonlinear Equations

This paper is devoted to globally convergent methods for solving large sparse systems of nonlinear equations with an inexact approximation of the Jacobian matrix. These methods include difference versions of the Newton method and various quasi-Newton methods. We propose a class of trust region methods together with a proof of their global convergence and describe an implementable globally convergent algorithm which can be used as a realization of these methods. Considerable attention is concentrated on the application of conjugate gradient-type iterative methods to the solution of linear subproblems. We prove that both the GMRES and the smoothed COS well-preconditioned methods can be used for the construction of globally convergent trust region methods. The efficiency of our algorithm is demonstrated computationally by using a large collection of sparse test problems.     

New second derivative multistep methods for stiff systems

In this paper we present details of a new class of second derivative multistep methods. Stability analysis is discussed and an improvement in stability region is obtained. With a simple modification we take advantage of calling for the solution of algebraic equations with the same coefficient matrix in each step. Moreover, using IOM to solve the resulting linear systems, the coefficient matrix is not needed explicitly. Some numerical experiments and comparison with several popular codes are given, showing strong superiority of this new class of methods.     

一类线性抛物型方程组的交替方向多步法及其理论分析

Efficient multistep procedure for time-stepping Galerkin method in which we use an alternating direction preconditioned iterative methods for approximately solving the linear equations arising at each timestep in a discrete Galerkin method for a class of linear parabolic systems is derived and analyzed. The optimal order error estimate is obtained. Numerical experiments show that the method has the characteristics of high efficiency and high accuracy.     

Tensor-Krylov methods for large nonlinear equations

In this paper, we describe tensor methods for large systems of nonlinear equations based on Krylov subspace techniques for approximately solving the linear systems that are required in each tensor iteration. We refer to a method in this class as a tensor-Krylov algorithm. We describe comparative testing for a tensor-Krylov implementation versus an analogous implementation based on a Newton-Krylov method. The test results show that tensor-Krylov methods are much more efficient and robust than Newton-Krylov methods on hard nonlinear equations problems.Part of this work was performed while the author was research associate at CERFACS (Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique).Research supported in part by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Block s‐step Krylov iterative methods

Block (including s‐step) iterative methods for (non)symmetric linear systems have been studied and implemented in the past. In this article we present a (combined) block s‐step Krylov iterative method for nonsymmetric linear systems. We then consider the problem of applying any block iterative method to solve a linear system with one right‐hand side using many linearly independent initial residual vectors. We present a new algorithm which combines the many solutions obtained (by any block iterative method) into a single solution to the linear system. This approach of using block methods in order to increase the parallelism of Krylov methods is very useful in parallel systems. We implemented the new method on a parallel computer and we ran tests to validate the accuracy and the performance of the proposed methods. It is expected that the block s‐step methods performance will scale well on other parallel systems because of their efficient use of memory hierarchies and their reduction of the number of global communication operations over the standard methods. Copyright © 2009 John Wiley & Sons, Ltd.     

On the practical value of the notion ofBN-stability

The oldest concept of unconditional stability of numerical integration methods for ordinary differential systems is that ofA-stability. This concept is related to linear systems having constant coefficients and has been introduced by Dahlquist in 1963. More recently, since another contribution of Dahlquist in 1975, there has been much interest in unconditional stability properties of numerical integration methods when applied to non-linear dissipative systems (G-stability,BN-stability,A-contractivity). Various classes of implicit Runge-Kutta methods have already been shown to beBN-stable. However, contrary to the property ofA-stability, when implementing such a method for practical use this unconditional stability property may be lost. The present note clarifies this for a class of diagonally implicit methods and shows at the same time that Rosenbrock's method is notBN-stable.     

Adaptive solution of infinite linear systems by Krylov subspace methods

In this paper we consider the problem of approximating the solution of infinite linear systems, finitely expressed by a sparse coefficient matrix. We analyse an algorithm based on Krylov subspace methods embedded in an adaptive enlargement scheme. The management of the algorithm is not trivial, due to the irregular convergence behaviour frequently displayed by Krylov subspace methods for nonsymmetric systems. Numerical experiments, carried out on several test problems, indicate that the more robust methods, such as GMRES and QMR, embedded in the adaptive enlargement scheme, exhibit good performances.     

General linear methods with external stages of different orders

The approach introduced recently by Albrecht to derive order conditions for Runge-Kutta formulas based on the theory of A-methods is also very powerful for the general linear methods. In this paper, using Albrecht's approach, we formulate the general theory of order conditions for a class of general linear methods where the components of the propagating vector of approximations to the solution have different orders. Using this theory we derive a class of diagonally implicit multistage integration methods (DIMSIMs) for which the global order is equal to the local order. We also derive a class of general linear methods with two nodal approximations of different orders which facilitate local error estimation. Our theory also applies to the class of two-step Runge-Kutta introduced recently by Jackiewicz and Tracogna.The work of the first author was supported by the National Science Foundation under grant NSF DMS-9208048. The work of the second author was supported by the Italian Consiglio Nazionale delle Richerche.     

A necessary and sufficient convergence condition of orthomin(k) methods for least squares problem with weight

A class of Orthomin-type methods for linear systems based on conjugate residuals is extended to a form suitable for solving a least squares problem with weight. In these algorithms a mapping matrix as preconditioner is brought into use. We also give a necessary and sufficient condition for the convergence of the algorithm. Furthermore, we also study the construction of the mapping matrix for which the necessary and sufficient condition holds.