Search

Presents an implementation of Stiefel's exchange algorithm for determining a Chebyshev solution to an overdetermined system of linear equations. Use of Gaussian LU decomposition with row interchanges; Stability of implementation than those usually given in the literature; Generalization of Stiefel's algorithm which permits the occasional exchange of two equations simultaneously.

Presents the theoretical background for a standard computer implementation based upon the LU decomposition. Criticism of Dantzig's simplex method for linear programming; Round-off error behavior of the LU implementation; Basis of computer implementations using Dantzig's simplex method.

Abstract: As an application of the symmetric-triangular (ST) decomposition given by Golub and Yuan (2001) and Strang (2003), three block ST preconditioners are discussed here for saddle point problems. All three preconditioners transform saddle point problems into a symmetric and positive definite system. The condition number of the three symmetric and positive definite systems are estimated. Therefore, numerical methods for symmetric and positive definite systems can be applied to solve saddle point problems indirectly. A numerical example for the symmetric indefinite system from the finite element approximation to the Stokes equation is given. Finally, some comments are given as well.

Large linear systems of saddle point type arise in a wide variety of applications throughout computational science and engineering. Due to their indefiniteness and often poor spectral properties, such linear systems represent a significant challenge for solver developers. In recent years there has been a surge of interest in saddle point problems, and numerous solution techniques have been proposed for this type of system. The aim of this paper is to present and discuss a large selection of solution methods for linear systems in saddle point form, with an emphasis on iterative methods for large and sparse problems.

Summary. We study the role of preconditioning strategies recently developed for coercive problems in connection with a two-step iterative method, based on the Hermitian skew-Hermitian splitting (HSS) of the coefficient matrix, proposed by Bai, Golub and Ng for the solution of nonsymmetric linear systems whose real part is coercive. As a model problem we consider Finite Differences (FD) matrix sequences { A n( a, p)} n discretizing the elliptic (convection-diffusion) problem with Ω being a plurirectangle of R d with a( x) being a uniformly positive function and p( x) denoting the Reynolds function: here for plurirectangle we mean a connected union of rectangles in d dimensions with edges parallel to the axes. More precisely, in connection with preconditioned HSS/GMRES like methods, we consider the preconditioning sequence { P n( a)} n, P n( a):= D n 1/2( a) A n(1,0) D n 1/2( a) where D n( a) is the suitably scaled main diagonal of A n( a,0). If a( x) is positive and regular enough, then the preconditioned sequence shows a strong clustering at unity so that the sequence { P n( a)} n turns out to be a superlinear preconditioning sequence for { A n( a,0)} n where A n( a,0) represents a good approximation of Re( A n( a, p)) namely the real part of A n( a, p). The computational interest is due to the fact that the preconditioned HSS method has a convergence behavior depending on the spectral properties of { P n -1( a)Re( A n( a, p))} n≈ { P n -1( a) A n( a,0)} n: therefore the solution of a linear system with coefficient matrix A n( a, p) is reduced to computations involving diagonals and to the use of fast Poisson solvers for { A n(1,0)} n. Some numerical experimentations confirm the optimality of the discussed proposal and its superiority with respect to existing techniques.

Summary. For the positive semidefinite system of linear equations of a block two-by-two structure, by making use of the Hermitian/skew-Hermitian splitting iteration technique we establish a class of preconditioned Hermitian/skew-Hermitian splitting iteration methods. Theoretical analysis shows that the new method converges unconditionally to the unique solution of the linear system. Moreover, the optimal choice of the involved iteration parameter and the corresponding asymptotic convergence rate are computed exactly. Numerical examples further confirm the correctness of the theory and the effectiveness of the method.

In this paper, we derive an object‐oriented parallel algorithm for three‐dimensional isopycnal flow simulations. The matrix formulation is central to the algorithm. It enables us to apply an efficient preconditioned conjugate gradient linear solver for the global system of equations, and leads naturally to an object‐oriented data structure design and parallel implementation. We discuss as well, in less detail, a similar algorithm based on the reduced system, suitable also for parallel computation. Favorable performances are observed on test problems. Copyright © 2002 John Wiley & Sons, Ltd.

An inverse eigenvalue problem concerns the reconstruction of a structured matrix from prescribed spectral data. Such an inverse problem arises in many applications where parameters of a certain physical system are to be determined from the knowledge or expectation of its dynamical behaviour. Spectral information is entailed because the dynamical behaviour is often governed by the underlying natural frequencies and normal modes. Structural stipulation is designated because the physical system is often subject to some feasibility constraints. The spectral data involved may consist of complete or only partial information on eigenvalues or eigenvectors. The structure embodied by the matrices can take many forms. The objective of an inverse eigenvalue problem is to construct a matrix that maintains both the specific structure as well as the given spectral property. In this expository paper the emphasis is to provide an overview of the vast scope of this intriguing problem, treating some of its many applications, its mathematical properties, and a variety of numerical techniques.

Summary The problem of generating the recurrence coefficients of orthogonal polynomials from the moments or from modified moments of the weight function is well understood for positive weight distributions. Here we extend this theory and the basic algorithms to the case of an indefinite weight function. While the generic indefinite case is formally not much different from the positive definite case, there exist nongeneric degenerate situations, and these require a different more complicated treatment. The understanding of these degenerate situations makes it possible to construct a stable approximate solution of an ill-conditioned problem.

Orthogonal polynomials are conveniently represented by the tridiagonal Jacobi matrix of coefficients of the recurrence relation which they satisfy. LetJ1 andJ2 be finite Jacobi matrices for the weight functionsw1 andw2, resp. Is it possible to determine a Jacobi matrix , corresponding to the weight functions =w1+w2 using onlyJ1 andJ2 and if so, what can be said about its dimension? Thus, it is important to clarify the connection between a finite Jacobi matrix and its corresponding weight function(s). This leads to the need for stable numerical processes that evaluate such matrices.

In this note, we discuss the reconstruction of periodic Jacobi matrices from spectral data. The method combines ideas and techniques from the algorithms given by Boley and Golub [1], [2], and Ferguson [3], resulting in a numerically stable algorithm applicable to a larger class of problems. The number of initial data items needed for this method equals the number of items in the resulting matrix, namely 2n.

Fitting circles and ellipses to given points in the plane is a problem that arises in many application areas, e.g., computer graphics, coordinate meteorology, petroleum engineering, statistics. In the past, algorithms have been given which fit circles and ellipses insome least-squares sense without minimizing the geometric distance to the given points.

This paper delineates the underlying theory of an efficient method for solving a class of specially-structured linear complementarity problems of potentially very large size. We propose a block-iterative method in which the subproblems are linear complementarity problems. Problems of the type considered here arise in the process of making discrete approximations to differential equations in the presence of special side conditions. This problem source is exemplified by the free boundary problem for finite-length journal bearings. Some of the authors' computational experience with the method is presented.

For an n-state finite, homogeneous, ergodic Markov chain, with transition matrix ${\bf P}$ and stationary distribution ${\boldsymbol \pi} $ we assume that the entries of ${\bf P}$ are differentiable functions of a parameter tand we obtain an expression for $d{\boldsymbol \pi} /dt$. This expression is given in terms of the group inverse of ${\bf I} - {\bf P}$ and is used in a sensitivity analysis of ${\boldsymbol \pi}$. Finally, it is demonstrated how a ${\boldsymbol QR}$ factorization can be used to simultaneously compute the stationary distribution of an ergodic chain along with estimates which gauge the sensitivity of the stationary distribution to perturbations in the transition probabilities.

We describe a procedure for determining estimates of the eigenvalues of operators used in various iterative methods for the solution of linear systems of equations. We also show how to determine upper and lower bounds for the error in the approximate solution of linear equations, using essentially the same information as that needed for the eigenvalue calculations. The methods described depend strongly upon the theory of moments and Gauss quadrature.

We study iterative methods for solving linear systems of the type arising from two-cyclic discretizations of non-self-adjoint two-dimensional elliptic partial differential equations. A prototype is the convection-diffusion equation. The methods consist of applying one step of cyclic reduction, resulting in a "reduced system" of half the order of the original discrete problem, combined with a reordering and a block iterative technique for solving the reduced system. For constant-coefficient problems, we present analytic bounds on the spectral radii of the iteration matrices in terms of cell Reynolds numbers that show the methods to be rapidly convergent. In addition, we describe numerical experiments that supplement the analysis and that indicate that the methods compare favorably with methods for solving the "unreduced" system.

We perform an analytic and experimental study of line iterative methods for solving linear systems arising from finite difference discretizations of non-self-adjoint elliptic partial differential equations on two-dimensional domains. The methods consist of performing one step of cyclic reduction, followed by solution of the resulting reduced system by line relaxation. We augment previous analyses of one-line methods, and we derive a new convergence analysis for two-line methods, showing that both classes of methods are highly effective for solving the convection-diffusion equation. In addition, we compare the experimental performance of several variants of these methods, and we show that the methods can be implemented efficiently on parallel architectures.

We consider the problem of generating the recursion coefficients of orthogonal polynomials for a given weight function. The weight function is assumed to be the weighted sum of weight functions, each supported on its own interval. Some of these intervals may coincide, overlap or are contiguous. We discuss three algorithms. Two of them are based on modified moments, whereas the other is based on an explicit expression for the desired coefficients. Several examples, illustrating the numerical performance of the various methods, are presented.

Summary We consider the following problem: Compute a vectorx such that ?Ax-b?2=min, subject to the constraint ?x?2=a. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse.

Summary The Chebyshev and second-order Richardson methods are classical iterative schemes for solving linear systems. We consider the convergence analysis of these methods when each step of the iteration is carried out inexactly. This has many applications, since a preconditioned iteration requires, at each step, the solution of a linear system which may be solved inexactly using an “inner” iteration. We derive an error bound which applies to the general nonsymmetric inexact Chebyshev iteration. We show how this simplifies slightly in the case of a symmetric or skew-symmetric iteration, and we consider both the cases of underestimating and overestimating the spectrum. We show that in the symmetric case, it is actually advantageous to underestimate the spectrum when the spectral radius and the degree of inexactness are both large. This is not true in the case of the skew-symmetric iteration. We show how similar results apply to the Richardson iteration. Finally, we describe numerical experiments which illustrate the results and suggest that the Chebyshev and Richardson methods, with reasonable parameter choices, may be more effective than the conjugate gradient method in the presence of inexactness.

Summary.: We derive analytic bounds on the convergence factors associated with block relaxation methods for solving the discrete two-dimensional convection-diffusion equation. The analysis applies to the reduced systems derived when one step of block Gaussian elimination is performed on red-black ordered two-cyclic discretizations. We consider the case where centered finite difference discretization is used and one cell Reynolds number is less than one in absolute value and the other is greater than one. It is shown that line ordered relaxation exhibits very fast rates of convergence.

The application of the Richardson second order iterative method to positive definite, symmetric linear equations is investigated. Absolute and statistical bounds for the round-off error are derived. The statistical theory agrees well with numerical experiments, until the accumulated round-off error becomes of the order of magnitude of the error in the computed solution. After this point the statistical dependence between the local round-off errors makes the observed variances larger than the theoretical variances.

Several algorithms are given and compared for computing Gauss quadrature rules. It is shown that given the three term recurrence relation for the orthogonal polynomials generated by the weight function, the quadrature rule may be generated by computing the eigenvalues and first component of the orthornormalized eigenvectors of a symmetric tridiagonal matrix. An algorithm is also presented for computing the three term recurrence relation from the moments of the weight function.

Assume that two subspaces F and G of a unitary space are defined as the ranges (or null spaces) of given rectangular matrices A and B. Accurate numerical methods are developed for computing the principal angles $ {\theta _k}(F,G)$ $ {u_k} \in F$ $ {v_k} \in G,k = 1,2, \cdots ,q = \dim (G) \leqq \dim (F)$ $ {\sigma _k} = \cos {\theta _k}$ $ {\theta _k}$ $ \max (\kappa (A),\kappa (B))$ denotes the condition number of a matrix. The algorithms are based on a preliminary QR-factorization of A and B (or $ {A^H}$), for which either the method of Householder transformations (HT) or the modified Gram-Schmidt method (MGS) is used. Then $ \cos \;{\theta _k}$ $ \sin \;{\theta _k}$ $ {\theta _k}$A and/or B are rank deficient is discussed.

Sommario SiaA una matrice reale simmetrica di ordinen, B una matrice reale simmetrica di ordinen per cuixTBx>0 eC una matricen×p di rangor conr=p

Motivation: Gene expression data often contain missing expression values. Effective missing value estimation methods are needed since many algorithms for gene expression data analysis require a complete matrix of gene array values. In this paper, imputation methods based on the least squares formulation are proposed to estimate missing values in the gene expression data, which exploit local similarity structures in the data as well as least squares optimization process. Results: The proposed local least squares imputation method (LLSimpute) represents a target gene that has missing values as a linear combination of similar genes. The similar genes are chosen by k-nearest neighbors or k coherent genes that have large absolute values of Pearson correlation coefficients. Non-parametric missing values estimation method of LLSimpute are designed by introducing an automatic k-value estimator. In our experiments, the proposed LLSimpute method shows competitive results when compared with other imputation methods for missing value estimation on various datasets and percentages of missing values in the data. Availability: The software is available at http://www.cs.umn.edu/~hskim/tools.html Contact: hpark@cs.umn.edu