Search

Abstract: In this paper, we apply a complete pivoting strategy to compute the left-looking version of AINV preconditioner for linear systems. As the preprocessing, the MultiLevel Nested Dissection reordering has also been applied. We have used this preconditioner as the right preconditioner for several linear systems where the coefficient matrices have been downloaded from the University of Florida Sparse Matrix Collection. Numerical experiments presented in this paper indicate the effectiveness of such a complete pivoting on the quality of left-looking version of AINV preconditioner. [Copyright &y& Elsevier]

Some preconditioners for accelerating the classical iterative methods are given in Zhang et al. [Y. Zhang and T.Z. Huang, A class of optimal preconditioners and their applications, Proceedings of the Seventh International Conference on Matrix Theory and Its Applications in China, 2006. Y. Zhang, T.Z. Huang, and X.P. Liu, Modified iterative methods for nonnegative matrices and M-matrices linear systems, Comput. Math. Appl. 50 (2005), pp. 1587-1602. Y. Zhang, T.Z. Huang, X.P. Liu, A class of preconditioners based on the (I+S(α))-type preconditioning matrices for solving linear systems, Appl. Math. Comp. 189 (2007), pp. 1737-1748]. Another kind of preconditioners approximating the inverse of a symmetric positive definite matrix was given in Simons and Yao [G. Simons, Y. Yao, Approximating the inverse of a symmetric positive definite matrix, Linear Algebra Appl. 281 (1998), pp. 97-103]. Zhang et al. 's preconditioners and Simons and Yao's are generalized in this paper. These preconditioners are all of low construction cost, which all could be taken as approximate inverse of M-matrices. Numerical experiments of these preconditioners applied with Krylov subspace methods show the effectiveness and performance, which also show that the preconditioners proposed in this paper are better approximate inverse for M-matrices than Simons'. [ABSTRACT FROM AUTHOR]

Abstract: Recently, Shen et al. has published a paper concerning the properties and computations of matrix pseudospectra. However, some of the main results seem to be incomplete. As a complement of the paper, in this note we first make several examples to show the incompleteness of that results, then we give the modified results through giving more appropriate definitions replacing the one given in [Y. Shen, J. Zhao, H. Fan, Properties and computations of matrix pseudospectra, Applied Mathematics and Computation 161 (2005) 385–393]. An interesting inclusion theorem for pseudospectra is given, which provides preferable bounds for standard pseudospectra. Some other properties are also explored. [Copyright &y& Elsevier]

Families of matrices smoothly depending on a vector of parameters are considered. Arnold [Russian Math. Surveys, 26 (1971), pp. 29–43] and Galin [Uspekhi Mat. Nauk, 27 (1972),pp. 241–242] have found and listed normal forms of families of complex and real matrices (miniversal deformations), to which any family of matrices can be transformed in the vicinity of a point in the parameter space by a change of basis, smoothly dependent on a vector of parameters, and by a smooth change of parameters. In this paper a constructive method of determining functions describing a change of basis and a change of parameters, transforming an arbitrary family to the miniversal deformation, is suggested. Derivatives of these functions with respect to parameters are determined from a recurrent procedure using derivatives of the functions of lower orders and derivatives of the family of matrices. Then the functions are found as Taylor series. Examples are given. The suggested method allows using efficiently miniversal deformations for investigation of different properties of matrix families. This is shown in the paper where tangent cones (linear approximations) to the stability domain at the singular boundary points are found. [ABSTRACT FROM AUTHOR]

This paper discusses the eigenvalue problem for the real symmetric matrix, especially the determination of the largest eigenvalue. The largest eigenvalue is the maximum extremum of the objective function called the Rayleigh quotient and can be determined by the steepest descent method. It is known, however, that the steepest descent method suffers from slow convergence because it converges linearly. Especially, when the largest and the nest largest eigenvalues have very close values, the convergence is particularly slow. This paper analyzes this situation and shows that the convergence can be accelerated by combining the steepest descent method with a technique called shaking. Finally, it is demonstrated by a numerical example that the convergence is accelerated drastically by the proposed technique. [ABSTRACT FROM AUTHOR]

The paper investigates classes of words equivalent under different ways of counting subwords. We present a general method of constructing sequences of equivalent words. Apart from obtaining numerical characterizations of words, we also construct sequences of words generating equal arithmetical power sums. Our notions of equivalence include the Parikh equivalence resulting from Parikh matrices, recently widely studied. Consequently, we are able to settle some open problems in this area. [ABSTRACT FROM AUTHOR]

The paper investigates the inclusion intervals of matrix singular values. By employing the digraph of a matrix, some new inclusion intervals of matrix singular values are presented. These intervals are based mainly on the use of positive scale vectors and their intersections. Theoretic analysis and numerical examples show that these results improve and generalize some known results of Li et al. (Numer. Linear Algebra Appl. 2007; 14(2):115–128) and Kolotilina (J. Math. Sci. 2006; 137(3):4794–4800). Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, based on Patel's algorithm (1993), we propose a structure-preserving algorithm for solving palindromic quadratic eigenvalue problems (QEPs). We also show the relationship between the structure-preserving algorithm and the URV-based structure-preserving algorithm by Schröder (2007). For large sparse palindromic QEPs, we develop a generalized T-skew-Hamiltonian implicitly restarted shift-and-invert Arnoldi algorithm for solving the resulting T-skew-Hamiltonian pencils. Numerical experiments show that our proposed structure-preserving algorithms perform well on the palindromic QEP arising from a finite element model of high-speed trains and rails. [ABSTRACT FROM AUTHOR]

Scaling is a commonly used technique for standard eigenvalue problems to improve the sensitivity of the eigenvalues. In this paper we investigate scaling for generalized and polynomial eigenvalue problems (PEPs) of arbitrary degree. It is shown that an optimal diagonal scaling of a PEP with respect to an eigenvalue can be described by the ratio of its normwise and componentwise condition number. Furthermore, the effect of linearization on optimally scaled polynomials is investigated. We introduce a generalization of the diagonal scaling by Lemonnier and Van Dooren to PEPs that is especially effective if some information about the magnitude of the wanted eigenvalues is available and also discuss variable transformations of the type λ = αμ for PEPs of arbitrary degree. [ABSTRACT FROM AUTHOR]

We study high order numerical quadratures to one dimensional delta function integrals in this paper. This is motivated by the fact that traditional numerical quadratures give only first order accuracy in general. We provide criteria on discrete delta functions and support size formulas which ensure any desired accuracy of the numerical quadratures. Discrete delta functions and support size formulas satisfying these criteria are designed. Numerical examples are presented to verify the performed analysis and the high order accuracy of the proposed numerical quadratures. [ABSTRACT FROM AUTHOR]

This paper presents an approach to transform asymmetric systems into symmetric systems by equivalence transformation and discusses what forms of restrictions should be imposed on the system matrices so that they can be simultaneously transformed into symmetric matrices. Conditions of symmetrizability obtained here are more "liberal" and numerical calculations of this transformation are more straightforward. Several examples are provided to illustrate the new approach. [ABSTRACT FROM AUTHOR]

This paper suggests a new method, called AINV-A, for constructing sparse approximate inverse preconditioners for positive-definite matrices, which can be regarded as a modification of the AINV method proposed by Benzi and Túma. Numerical results on SPD test matrices coming from different applications demonstrate the robustness of the AINV-A method and its superiority to the original AINV approach. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the iterative solution of ill-conditioned Toeplitz systems generated by continuous nonnegative real-valued functions f with a finite number of zeros. We construct new w-circulant preconditioners without explicit knowledge of the generating function f by approximating f by its convolution f * KN with a suitable positive reproducing kernel KN. By the restriction to positive kernels we obtain positive definite preconditioners. Moreover, if f has only zeros of even order ≤ 2s, then we can prove that the property [This symbol cannot be presented in ASCII format]π-π t2k KN(t)dt ≤ CN-2k (k = 0, … ,s) of the kernel is necessary and sufficient to ensure the convergence of the PCG method in a number of iteration steps independent of the dimension N of the system. Our theoretical results were confirmed by numerical tests. [ABSTRACT FROM AUTHOR]

In this paper we exhibit, under suitable conditions, a neat relationship between the Moore­Penrose generalized inverse of a sum of two matrices and the Moore­Penrose generalized inverses of the individual terms. We include an application to the parallel sum of matrices. [ABSTRACT FROM AUTHOR]

This paper gives a quantitative result that if A is a substochastic matrix and has r eigenvalues which are sufficiently close to 1, then A has r disjoint principal submatrices which are nearly stochastic. [ABSTRACT FROM AUTHOR]

This paper extends the author's earlier work which proved that, for a certain class of Hermitian eigenproblems AP = λBP (including, most notably, the Toeplitz eigenproblem), the eigenvectors can be represented as saddlepoints of a special form of the Rayleigh quotient. Each saddlepoint solves a min-max/max-min optimization problem whose optimal value is the eigenvalue. The zeros of the eigenpolynomial factors are located with respect to the unit circle. These results were proved, in part, by using an inertia theorem for Stein equations. For another class of Hermitian eigenproblems AP = λBP, an analogous set of results are derived here using an inertia theorem for Lyapunov equations. In this case, the zeros of the eigenpolynomial factors are located with respect to the imaginary axis, and sufficient conditions for the eigenpolynomial factors to have only extended imaginary zeros are established. The highlight of the article is an important theorem that yields a general factorization of saddlepoint eigenpolynomials and parameterizes all eigenvector saddlepoint representations for an m-dimensional eigenspace. Several key extensions to the theory are also presented. [ABSTRACT FROM AUTHOR]

In this paper we provide an actual bound for the distance between the original and the perturbed right singular vector subspaces of a general matrix with full column rank. We also provide actual relative componentwise bounds for perturbed eigenvectors of a positive definite matrix. [ABSTRACT FROM AUTHOR]

Superlinear preconditioners (those that provide a proper cluster at 1) are very important for the cg-like methods since they make these methods converge superlinearly. As is well known, for Toeplitz matrices generated by a continuous symbol, many circulant and circulant-like (related to different matrix algebras) preconditioners were proved to be superlinear. In contrast, for multilevel Toeplitz matrices there has been no proof of the superlinearity of any multilevel circulants. In this paper we show that such a proof is not possible since any multilevel circulant preconditioner is not superlinear, in the general case of multilevel Toeplitz matrices. Moreover, for matrices not necessarily Toeplitz, we present some general results proving that many popular structured preconditioners cannot be superlinear. [ABSTRACT FROM AUTHOR]

Let WN = WN(z1,z2,…,zn) be a rectangular Vandermonde matrix of order n×N, N ≥ n, with distinct nodes zj in the unit disk and zjk-1 as its (j,k) entry. Matrices of this type often arise in frequency estimation and system identification problems. In this paper, the conditioning of WN is analyzed and bounds for the spectral condition numberk2(WN) are derived. The bounds depend on n, N, and the separation of the nodes. By analyzing the behavior of the bounds as functions of N, we conclude that these matrices may become well conditioned, provided the nodes are close to the unit circle but not extremely close to each other and provided the number of columns of WN is large enough. The asymptotic behavior of both the conditioning itself and the bounds is analyzed and the theoretical results arising from this analysis verified by numerical examples. [ABSTRACT FROM AUTHOR]

In this paper we consider real or complex skew-Hamiltonian/Hamiltonian pencils λS - H, i.e., pencils where S is a skew-Hamiltonian and H is a Hamiltonian matrix. These pencils occur, for example, in the theory of continuous time, linear quadratic optimal control problems. We reduce these pencils to canonical and Schur-type forms under structure-preserving transformations, i.e., J-congruence-transformations (λS-H) → -JP*J(λS-H)P, where P is nonsingular or unitary. [ABSTRACT FROM AUTHOR]