New Estimates for the Rate of Convergence of the Method of Subspace Corrections

We discuss estimates for the rate of convergence of the method of successive subspace corrections in terms of condition number estimate for the method of parallel subspace corrections. We provide upper bounds and in a special case, a lower bound for preconditioners defined via the method of successive subspace corrections.     

The method of alternating projections and the method of subspace corrections in Hilbert space

A new identity is given in this paper for estimating the norm of the product of nonexpansive operators in Hilbert space. This identity can be applied for the design and analysis of the method of alternating projections and the method of subspace corrections. The method of alternating projections is an iterative algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces by alternatively computing the best approximations from the individual subspaces which make up the intersection. The method of subspace corrections is an iterative algorithm for finding the solution of a linear equation in a Hilbert space by approximately solving equations restricted on a number of closed subspaces which make up the entire space. The new identity given in the paper provides a sharpest possible estimate for the rate of convergence of these algorithms. It is also proved in the paper that the method of alternating projections is essentially equivalent to the method of subspace corrections. Some simple examples of multigrid and domain decomposition methods are given to illustrate the application of the new identity.

     

Efficient methods for the inclusion of polynomial zeros

Using a suitable zero-relation and the inclusion isotonicity property, new interval iterative methods for the simultaneous inclusion of simple complex zeros of a polynomial are derived. These methods produce disks in the complex plane that contain the polynomial zeros in each iteration, providing in this manner an information about upper error bounds of approximations. Starting from the basic method of the fourth order, two accelerated methods with Newton’s and Halley’s corrections, having the order of convergence five and six respectively, are constructed. This increase of the convergence rate is obtained without any additional operations, which means that the methods with corrections are very efficient. The convergence analysis of the basic method and the methods with corrections is performed under computationally verifiable initial conditions, which is of practical importance. Two numerical examples are presented to demonstrate the convergence behavior of the proposed interval methods.     

Multiple centrality corrections in a primal-dual method for linear programming

A modification of the (infeasible) primal-dual interior point method is developed. The method uses multiple corrections to improve the centrality of the current iterate. The maximum number of corrections the algorithm is encouraged to make depends on the ratio of the efforts to solve and to factorize the KKT systems. For any LP problem, this ratio is determined right after preprocessing the KKT system and prior to the optimization process. The harder the factorization, the more advantageous the higher-order corrections might prove to be.The computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real-life LP models arising from applications. The use of multiple centrality corrections gives on the average a 25% to 40% reduction in the number of iterations compared with the widely used second-order predictor-corrector method. This translates into 20% to 30% savings in CPU time.Supported by the Fonds National de la Recherche Scientifique Suisse, Grant #12-34002.92.     

A sharp convergence estimate for the method of subspace corrections for singular systems of equations

This paper is devoted to the convergence rate estimate for the method of successive subspace corrections applied to symmetric and positive semidefinite (singular) problems. In a general Hilbert space setting, a convergence rate identity is obtained for the method of subspace corrections in terms of the subspace solvers. As an illustration, the new abstract theory is used to show uniform convergence of a multigrid method applied to the solution of the Laplace equation with pure Neumann boundary conditions.

     

A variation on the interior point method for linear programming using the continued iteration

In this paper, we present a proposal for a variation of the predictor–corrector interior point method with multiple centrality corrections. The new method uses the continued iteration to compute a new search direction for the predictor corrector method. The purpose of incorporating the continued iteration is to reduce the overall computational cost required to solve a linear programming problem. The computational results constitute evidence of the improvement obtained with the use of this technique combined with the interior point method.     

Regularization Using QR Factorization and the Estimation of the Optimal Parameter

In this paper we propose a direct regularization method using QR factorization for solving linear discrete ill-posed problems. The decomposition of the coefficient matrix requires less computational cost than the singular value decomposition which is usually used for Tikhonov regularization. This method requires a parameter which is similar to the regularization parameter of Tikhonov's method. In order to estimate the optimal parameter, we apply three well-known parameter choice methods for Tikhonov regularization.This revised version was published online in October 2005 with corrections to the Cover Date.     

Asymptotic convergence in a generalized predictor-corrector method

The asymptotic convergence properties of a generalized predictor-corrector method are analyzed. This method is based on making a sequence of corrections to the primal-dual affine scaling (predictor) direction. It is shown that a method makingr corrections to a predictor direction has theQ-order convergence of orderr+2. It is also shown that asymptotically the problem can be solved by only computing corrections to the predictor direction. Supported in part by a grant from the GTE Laboratories and by the grant CCR-9019469 from the National Science Foundation.     

Stability of the Matrix Factorization for Solving Block Tridiagonal Symmetric Indefinite Linear Systems

In this paper, we propose a new factorization method for block tridiagonal symmetric indefinite matrices. We also discuss the stability of the factorization method. As a measurement of stability, an effective condition number is derived by using backward error analysis and perturbation analysis. It shows that under some suitable assumptions, the solution obtained by this factorization method is acceptable. Numerical results demonstrate that the factorization is stable if its condition number is not too large. This revised version was published online in July 2006 with corrections to the Cover Date.     

A fast algorithm for solving Toeplitz penta-diagonal systems

In this paper a fast algorithm for solving a large system with a symmetric Toeplitz penta-diagonal coefficient matrix is presented. This efficient method is based on the idea of a system perturbation followed by corrections and is competitive with standard methods. The error analysis is also given.     

The self-validated method for polynomial zeros of high efficiency

The improved iterative method of Newton’s type for the simultaneous inclusion of all simple complex zeros of a polynomial is proposed. The presented convergence analysis, which uses the concept of the R-order of convergence of mutually dependent sequences, shows that the convergence rate of the basic third order method is increased from 3 to 6 using Ostrowski’s corrections. The new inclusion method with Ostrowski’s corrections is more efficient compared to all existing methods belonging to the same class. To demonstrate the convergence properties of the proposed method, two numerical examples are given.     

The Lanczos Method with Semi-Definite Inner Product

The spectral transformation Lanczos method is very popular for solving large scale real symmetric generalized eigenvalue problems. The method uses a special inner product so that the symmetric Lanczos method can be used. Sometimes, a semi-definite inner product must be used. This may lead to instabilities and break-down. In this paper, we suggest cures for breakdown by use of implicit restarting and the pseudo-Lanczos method.This revised version was published online in October 2005 with corrections to the Cover Date.     

Parallel constrained molecular dynamics

A block version of the Shake method for heavy atom simulation in biological systems is presented in this paper. The method solves successively, independent blocks of constraints of small size by a Newton method. This algorithm is implemented in TAKAKAW, an efficient parallel molecular dynamics code. This method has been tested on a small system and on an ionic canal of 67671 atoms. This revised version was published online in June 2006 with corrections to the Cover Date.     

The combinatorics of birth-death processes and applications to queues

In this paper we present a combinatorial technique which allows the derivation of the transition functions of general birth-death processes. This method provides a flexible tool for the transient analysis of Markovian queueing systems with state dependent transition rates, like M/M/c models or systems with balking and reneging. This revised version was published online in June 2006 with corrections to the Cover Date.     

Avoiding breakdown in Van der Vorst's method

Van der Vorst's method is a development of Lanczos' iterative method for the solution of a large sparse system of linear equations. Both methods can suffer from Lanczos breakdown. The usual cure for this problem is a look-ahead method. Recently, the look-around method has been proposed, which tracks the edges of blocks in degenerate cases instead of jumping across them. Here we show how Van der Vorst's minimal residual principle can be built into the look-around method. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Locally Conservative Eulerian-Lagrangian Finite Difference Method for a Parabolic Equation

The object of this paper is to define a finite difference analogue of a locally conservative Eulerian—Lagrangian method based on mixed finite elements and to prove its convergence. The method is appropriate for convection-dominated diffusive processes; here, it will be considered in the case of a semilinear parabolic equation in a single space variable.This revised version was published online in October 2005 with corrections to the Cover Date.     

Meson contributions in the Nambu-Jona-Lasinio model

We discuss the problem of calculating corrections to the mean-field approximation in the Nambu-Jona-Lasinio model. To calculate such corrections, we propose using the method of the Legendre transformation with respect to a bilocal source, which allows taking symmetry constraints related to the chiral Ward identity into account effectively. Using the proposed method, we determine the corrections to the quark propagator and the two-particle quark function. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 159, No. 1, pp. 81–95, April, 2009.     

Newton Generalized Hessenberg method for solving nonlinear systems of equations

In this paper, we give and analyze a Finite Difference version of the Generalized Hessenberg (FDGH) method. The obtained results show that applying this method in solving a linear system is equivalent to applying the Generalized Hessenberg method to a perturbed system. The finite difference version of the Generalized Hessenberg method is used in the context of solving nonlinear systems of equations using an inexact Newton method. The local convergence of the finite difference versions of the Newton Generalized Hessenberg method is studied. We obtain theoretical results that generalize those obtained for Newton-Arnoldi and Newton-GMRES methods. Numerical examples are given in order to compare the performances of the finite difference versions of the Newton-GMRES and Newton-CMRH methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

A new approach to Sheppard’s corrections

A very simple closed-form formula for Sheppard’s corrections is recovered by means of the classical umbral calculus. Using this symbolic method, a more general closed-form formula for discrete parent distributions is provided and the generalization to the multivariate case turns out to be straightforward. All these new formulas are particularly suited to be implemented in any symbolic package.