160 results
Search Results
2. Tight and efficient enclosure of matrix multiplication by using optimized BLAS.
- Author
-
Ozaki, Katsuhisa, Ogita, Takeshi, and Oishi, Shin'ichi
- Subjects
MULTIPLICATION ,MATHEMATICAL optimization ,MATRICES (Mathematics) ,ALGORITHMS ,NUMERICAL analysis ,FIXED point theory - Abstract
This paper is concerned with the tight enclosure of matrix multiplication AB for two floating-point matrices A and B. The aim of this paper is to compute component-wise upper and lower bounds of the exact result C of the matrix multiplication AB by floating-point arithmetic. Namely, an interval matrix enclosing C is obtained. In this paper, new algorithms for enclosing C are proposed. The proposed algorithms are designed to mainly exploit the level 3 operations in BLAS. Although the proposed algorithms take around twice as much costs as a standard algorithm promoted by Oishi and Rump, the accuracy of the result by the proposed algorithms is better than that of the standard algorithm. At the end of this paper, we present numerical examples showing the efficiency of the proposed algorithms. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
3. A fast convergent iterative solver for approximate inverse of matrices.
- Author
-
Soleymani, F.
- Subjects
STOCHASTIC convergence ,ITERATIVE methods (Mathematics) ,APPROXIMATION theory ,MATRIX inversion ,ALGORITHMS ,MATRICES (Mathematics) - Abstract
SUMMARY In this paper, a rapid iterative algorithm is proposed to find robust approximations for the inverse of nonsingular matrices. The analysis of convergence reveals that this high-order method possesses eighth-order convergence. The interesting point is that, this rate is attained using less number of matrix-by-matrix multiplications in contrast to the existing methods of the same type in the literature. The extension of the method for finding Moore-Penrose inverse of singular or rectangular matrices is also presented. Numerical comparisons will be given to show the applicability, stability and consistency of the new scheme by paying special attention on the computational time. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
4. An alternating direction method for linear-constrained matrix nuclear norm minimization.
- Author
-
Xiao, Yun-Hai and Jin, Zheng-Fen
- Subjects
LINEAR systems ,MATRICES (Mathematics) ,PROBLEM solving ,ITERATIVE methods (Mathematics) ,CONTROL theory (Engineering) ,MATHEMATICAL models ,LAGRANGIAN functions ,ALGORITHMS - Abstract
SUMMARY The aim of the nuclear norm minimization problem is to find a matrix that minimizes the sum of its singular values and satisfies some constraints simultaneously. Such a problem has received more attention largely because it is closely related to the affine rank minimization problem, which appears in many control applications including controller design, realization theory, and model reduction. In this paper, we first propose an exact version alternating direction method for solving the nuclear norm minimization problem with linear equality constraints. At each iteration, the method involves a singular value thresholding and linear matrix equations which are solved exactly. Convergence of the proposed algorithm is followed directly. To broaden the capacity of solving larger problems, we solve approximately the subproblem by an iterative method with the Barzilai-Borwein steplength. Some extensions to the noisy problems and nuclear norm regularized least-square problems are also discussed. Numerical experiments and comparisons with the state-of-the-art method FPCA show that the proposed method is effective and promising. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
5. Revisiting the matrix-free solution of Markov regenerative processes.
- Author
-
Amparore, Elvio Gilberto and Donatelli, Susanna
- Subjects
MARKOV processes ,MATRICES (Mathematics) ,ALGORITHMS ,INVARIANT subspaces ,APPROXIMATION theory ,RANDOM variables ,MATHEMATICAL models - Abstract
SUMMARY In this paper, we revisit the steady-state solution method for Markov Regenerative Processes (MRP) proposed in the work by German. This method solves the embedded Markov chain P of the MRP without storing the matrix P explicitly. We address three issues left open in German's Work: 1) the solution method is restricted to Power method; 2) it has been defined only for ergodic MRPs; and 3) no preconditioning is available to speed-up the computation. This paper discusses how to lift these limitations by extending the algorithm to preconditioned Krylov-subspace methods and by generalizing it to the non-ergodic case. An MRP-specific preconditioner is also proposed, which is built from a sparse approximation of the MRP matrix, computed via simulation. An experimental assessment of the proposed preconditioner is then provided. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
6. Short note: An integrable numerical algorithm for computing eigenvalues of a specially structured matrix.
- Author
-
Sun, Jian-Qing, Hu, Xing-Biao, and Tam, Hon-Wah
- Subjects
NUMERICAL analysis ,ALGORITHMS ,EIGENVALUES ,LATTICE theory ,ASYMPTOTIC expansions ,MATRICES (Mathematics) - Abstract
This paper is motivated by some recent work of Fukuda, Ishiwata, Iwasaki, and Nakamura ( Inverse Problems 2009; :015007). We first design an algorithm for computing the eigenvalues of a specially structured matrix from the discrete Bogoyavlensky Lattice 2 (dBL2) system. A Lax representation for the dBL2 system is given in a matrix form. By considering the asymptotic behavior of dBL2 variables, some characteristic polynomials are then factorized. A new algorithm for computing the complex eigenvalues of a specially structured matrix is then introduced. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
7. A backward stability analysis of diagonal pivoting methods for solving unsymmetric tridiagonal systems without interchanges.
- Author
-
Erway, Jennifer B. and Marcia, Roummel F.
- Subjects
FACTORIZATION ,MATRICES (Mathematics) ,COLUMNS ,GROWTH factors ,LINEAR systems ,LINEAR algebra ,ALGORITHMS - Abstract
This paper concerns the LBM factorization of unsymmetric tridiagonal matrices, where L and M are unit lower triangular matrices and B is block diagonal with 1×1 and 2×2 blocks. In some applications, it is necessary to form this factorization without row or column interchanges while the tridiagonal matrix is formed. Bunch and Kaufman proposed a pivoting strategy without interchanges specifically for symmetric tridiagonal matrices, and more recently, Bunch and Marcia proposed pivoting strategies that are normwise backward stable for linear systems involving such matrices. In this paper, we extend these strategies to the unsymmetric tridiagonal case and demonstrate that the proposed methods both exhibit bounded growth factors and are normwise backward stable. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
8. A smoothing Newton's method for the construction of a damped vibrating system from noisy test eigendata.
- Author
-
Bai, Zheng-Jian and Ching, Wai-Ki
- Subjects
VIBRATION (Mechanics) ,MASS (Physics) ,DAMPING (Mechanics) ,MATRICES (Mathematics) ,ALGORITHMS - Abstract
In this paper we consider an inverse problem for a damped vibration system from the noisy measured eigendata, where the mass, damping, and stiffness matrices are all symmetric positive-definite matrices with the mass matrix being diagonal and the damping and stiffness matrices being tridiagonal. To take into consideration the noise in the data, the problem is formulated as a convex optimization problem involving quadratic constraints on the unknown mass, damping, and stiffness parameters. Then we propose a smoothing Newton-type algorithm for the optimization problem, which improves a pre-existing estimate of a solution to the inverse problem. We show that the proposed method converges both globally and quadratically. Numerical examples are also given to demonstrate the efficiency of our method. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
9. Block-row Hankel weighted low rank approximation.
- Author
-
Schuermans, M., Lemmerling, P., and Van Huffel, S.
- Subjects
APPROXIMATION theory ,HANKEL functions ,MATRICES (Mathematics) ,MATHEMATICAL optimization ,ALGORITHMS - Abstract
This paper extends the weighted low rank approximation (WLRA) approach to linearly structured matrices. In the case of Hankel matrices with a special block structure, an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
10. O(N) algorithms for disordered systems.
- Author
-
Sacksteder, V. E.
- Subjects
ALGORITHMS ,ALGEBRA ,MATRICES (Mathematics) ,HAMILTONIAN systems ,DIFFERENTIABLE dynamical systems - Abstract
The past 13 years have seen the development of many algorithms for approximating matrix functions in O(N) time, where N is the basis size. These O(N) algorithms rely on assumptions about the spatial locality of the matrix function; therefore their validity depends very much on the argument of the matrix function. In this article I carefully examine the validity of certain O(N) algorithms when applied to Hamiltonians of disordered systems. I focus on the prototypical disordered system, the Anderson model. I find that O(N) algorithms for the density matrix function can be used well below the Anderson transition (i.e. in the metallic phase;) they fail only when the coherence length becomes large. This paper also includes some experimental results about the Anderson model's behaviour across a range of disorders. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
11. Tikhonov regularization of large symmetric problems.
- Author
-
Calvetti, D., Reichel, L., and Shuibi, A.
- Subjects
TOEPLITZ matrices ,MATRICES (Mathematics) ,SCHUR functions ,ALGORITHMS ,ALGEBRA - Abstract
Many popular solution methods for large discrete ill-posed problems are based on Tikhonov regularization and compute a partial Lanczos bidiagonalization of the matrix. The computational effort required by these methods is not reduced significantly when the matrix of the discrete ill-posed problem, rather than being a general nonsymmetric matrix, is symmetric and possibly indefinite. This paper describes new methods, based on partial Lanczos tridiagonalization of the matrix, that exploit symmetry. Computed examples illustrate that one of these methods can require significantly less computational work than available structure-ignoring schemes. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
12. Fast regularized structured total least squares algorithm for solving the basic deconvolution problem.
- Author
-
Mastronardi, N., Lemmerling, P., and Van Huffel, S.
- Subjects
DECONVOLUTION (Mathematics) ,SPECTRUM analysis ,LEAST squares ,MATHEMATICS ,MATHEMATICAL statistics ,SCHUR functions ,ALGORITHMS ,TOEPLITZ matrices ,MATRICES (Mathematics) - Abstract
In this paper, we develop a fast regularized structured total least squares (RSTLS) algorithm for solving the basic deconvolution problem. The algorithm is based on a particular implementation of the generalized Schur algorithm. We apply the new algorithm on a deconvolution problem arising in a medical application in renography. By means of this example, we show that regularization in the structured total least squares framework yields more accurate results compared to other estimators. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
13. Analysis of a circulant based preconditioner for a class of lower rank extracted systems.
- Author
-
Salapaka, S., Peirce, A., and Dahleh, M.
- Subjects
MATRICES (Mathematics) ,INTEGRAL equations ,CONJUGATE gradient methods ,TOEPLITZ matrices ,ALGORITHMS ,NUMERICAL solutions to equations - Abstract
This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, A
p x=b, which we call lower rank extracted systems (LRES), by the preconditioned conjugate gradient method. These systems correspond to integral equations with convolution kernels defined on a union of many line segments in contrast to only one line segment in the case of Toeplitz systems. The p × p matrix, Ap , is shown to be a principal submatrix of a larger N × N Toeplitz matrix, AN . The preconditioner is provided in terms of the inverse of a 2N × 2N circulant matrix constructed from the elements of AN . The preconditioner is shown to yield clustering in the spectrum of the preconditioned matrix similar to the clustering results for iterative algorithms used to solve Toeplitz systems. The analysis also demonstrates that the computational expense to solve LRE systems is reduced to O(N log N). Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
14. Maximum-weight-basis preconditioners.
- Author
-
Boman, Erik G., Chen, Doron, Hendrickson, Bruce, and Toledo, Sivan
- Subjects
MATRICES (Mathematics) ,ALGEBRA ,ALGORITHMS ,STOCHASTIC convergence ,NUMERICAL analysis - Abstract
This paper analyses a novel method for constructing preconditioners for diagonally dominant symmetric positive-definite matrices. The method discussed here is based on a simple idea: we construct M by simply dropping offdiagonal non-zeros from A and modifying the diagonal elements to maintain a certain row-sum property. The preconditioners are extensions of Vaidya's augmented maximum-spanning-tree preconditioners. The preconditioners presented here were also mentioned by Vaidya in an unpublished manuscript, but without a complete analysis. The preconditioners that we present have only O(n+t
2 ) nonzeros, where n is the dimension of the matrix and 1⩽t⩽n is a parameter that one can choose. Their construction is efficient and guarantees that the condition number of the preconditioned system is O(n2 /t2 ) if the number of nonzeros per row in the matrix is bounded by a constant. We have developed an efficient algorithm to construct these preconditioners and we have implemented it. We used our implementation to solve a simple model problem; we show the combinatorial structure of the preconditioners and we present encouraging convergence results. [ABSTRACT FROM AUTHOR]- Published
- 2004
- Full Text
- View/download PDF
15. Some observations on the l2 convergence of the additive Schwarz preconditioned GMRES method.
- Author
-
Xiao-Chuan Cai and Jun Zou
- Subjects
LINEAR algebra ,LINEAR systems ,STOCHASTIC convergence ,PARALLEL computers ,ALGORITHMS ,MATRICES (Mathematics) - Abstract
Additive Schwarz preconditioned GMRES is a powerful method for solving large sparse linear systems of equations on parallel computers. The algorithm is often implemented in the Euclidean norm, or the discrete l
2 norm, however, the optimal convergence result is available only in the energy norm (or the equivalent Sobolev H1 norm). Very little progress has been made in the theoretical understanding of the l2 behaviour of this very successful algorithm. To add to the difficulty in developing a full l2 theory, in this note, we construct explicit examples and show that the optimal convergence of additive Schwarz preconditioned GMRES in l2 cannot be obtained using the existing GMRES theory. More precisely speaking, we show that the symmetric part of the preconditioned matrix, which plays a role in the Eisenstat–Elman–Schultz theory, has at least one negative eigenvalue, and we show that the condition number of the best possible eigenmatrix that diagonalizes the preconditioned matrix, key to the Saad–Schultz theory, is bounded from both above and below by constants multiplied by h-1/2 . Here h is the finite element mesh size. The results presented in this paper are mostly negative, but we believe that the techniques used in our proofs may have wide applications in the further development of the l2 convergence theory and in other areas of domain decomposition methods. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2002
- Full Text
- View/download PDF
16. Iterative computation of derivatives of repeated eigenvalues and the corresponding eigenvectors.
- Author
-
Andrew, Alan L. and Tan, Roger C.E.
- Subjects
EIGENVALUES ,MATRICES (Mathematics) ,ITERATIVE methods (Mathematics) ,ALGORITHMS ,STOCHASTIC convergence ,LINEAR algebra - Abstract
Recently the authors proposed a simultaneous iteration algorithm for the computation of the partial derivatives of repeated eigenvalues and the corresponding eigenvectors of matrices depending on several real variables. This paper analyses the properties of that algorithm and extends it in several ways. The previous requirement that the repeated eigenvalue be dominant is relaxed, and the new generalized algorithm given here allows the simultaneous treatment of simple and repeated eigenvalues. Methods for accelerating convergence are examined. Numerical results support our theoretical analysis. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
17. A practical algorithm for faster matrix multiplication.
- Author
-
Kaporin, Igor
- Subjects
ALGORITHMS ,ALGEBRA ,FOUNDATIONS of arithmetic ,MATRICES (Mathematics) ,ABSTRACT algebra ,PARALLEL processing - Abstract
The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recursive one- or two-level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
18. Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start.
- Author
-
Leyk, Zbigniew and Woźniakowski, Henryk
- Subjects
EIGENVECTORS ,EIGENVALUES ,POLYNOMIALS ,ALGORITHMS ,ESTIMATION theory ,MATRICES (Mathematics) - Abstract
We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
19. New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
- Author
-
Li, Shengguo, Liao, Xiangke, Liu, Jie, and Jiang, Hao
- Subjects
EIGENVALUES ,MATRICES (Mathematics) ,CAUCHY problem ,ALGORITHMS ,APPROXIMATION theory - Abstract
In this paper, two accelerated divide-and-conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N
2 r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy-like matrices and are off-diagonally low-rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low-rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off-diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. [ABSTRACT FROM AUTHOR]- Published
- 2016
- Full Text
- View/download PDF
20. The modulus-based matrix splitting algorithms for a class of weakly nonlinear complementarity problems.
- Author
-
Huang, Na and Ma, Changfeng
- Subjects
MATRICES (Mathematics) ,ALGORITHMS ,SET theory ,NONLINEAR theories ,LINEAR complementarity problem ,BOUNDARY value problems ,FIXED point theory ,STOCHASTIC convergence - Abstract
In this paper, we study a class of weakly nonlinear complementarity problems arising from the discretization of free boundary problems. By reformulating the complementarity problems as implicit fixed-point equations based on splitting of the system matrices, we propose a class of modulus-based matrix splitting algorithms. We show their convergence by assuming that the system matrix is positive definite. Moreover, we give several kinds of typical practical choices of the modulus-based matrix splitting iteration methods based on the different splitting of the system matrix. Numerical experiments on two model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of our modulus-based matrix splitting algorithms. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
21. A new two-phase structure-preserving doubling algorithm for critically singular M-matrix algebraic Riccati equations.
- Author
-
Huang, Tsung Ming, Huang, Wei Qiang, Li, Ren Cang, and Lin, Wen Wei
- Subjects
ALGORITHMS ,MATHEMATICAL singularities ,MATRICES (Mathematics) ,ALGEBRAIC equations ,NUMERICAL solutions to Riccati equation ,ITERATIVE methods (Mathematics) - Abstract
Among numerous iterative methods for solving the minimal nonnegative solution of an M-matrix algebraic Riccati equation, the structure-preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank-one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank-one component can be accurately recovered. We then propose an efficient hybrid method, called the two-phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two-phase SDA saves those SDA iterative steps that previously have to have for the rank-one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two-phase SDA. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
22. Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis.
- Author
-
Kressner, Daniel and Roman, Jose E.
- Subjects
CHEBYSHEV polynomials ,ALGORITHMS ,MATRICES (Mathematics) ,PROBLEM solving ,EIGENVALUES ,NONLINEAR theories - Abstract
SUMMARY Novel memory-efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so-called quadratic Arnoldi method and two-level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift-and-invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
23. An algorithm for constructing a pseudo-Jacobi matrix from given spectral data.
- Author
-
Bebiano, N., Furtado, S., and Providência, J.
- Subjects
ALGORITHMS ,JACOBI method ,MATRICES (Mathematics) ,SPECTRAL theory ,QUANTUM theory ,TOPOLOGICAL spaces ,INDEFINITE inner product spaces - Abstract
SUMMARY The main purpose of this paper is the extension of the classical spectral direct and inverse analysis of Jacobi matrices for the non-self-adjoint setting. Matrices of this class appear in the context of non-Hermitian quantum mechanics. The reconstruction of a pseudo-Jacobi matrix from its spectrum and the spectra of two complementary principal matrices is investigated in the context of indefinite inner product spaces. An existence and uniqueness theorem is given, and a strikingly simple algorithm, based on the Euclidean division algorithm, to reconstruct the matrix from the spectral data is presented. A result of Friedland and Melkman stating a necessary and sufficient condition for a real sequence to be the spectrum of a non-negative Jacobi matrix is revisited and generalized. Namely, it is shown that a suitable set of prescribed eigenvalues defines a unique non-negative pseudo-Jacobi matrix, which is J-Hermitian for a fixed J. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
24. Direct algorithm for the solution of two-sided obstacle problems with M-matrix.
- Author
-
Jiang, Ying-Jun and Zeng, Jin-Ping
- Subjects
ALGORITHMS ,MATRICES (Mathematics) ,POLYNOMIALS ,COMPUTATIONAL complexity ,LINEAR complementarity problem ,PROBLEM solving ,GAUSSIAN processes - Abstract
A direct algorithm for the solution to the affine two-sided obstacle problem with an M-matrix is presented. The algorithm has the polynomial bounded computational complexity O( n) and is more efficient than those in ( Numer. Linear Algebra Appl. 2006; :543-551). Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
25. Solutions of symmetry-constrained least-squares problems.
- Author
-
Zhen-Yun Peng
- Subjects
ITERATIVE methods (Mathematics) ,LEAST squares ,ALGORITHMS ,MATHEMATICAL analysis ,LINEAR algebra ,MATRICES (Mathematics) - Abstract
In this paper, two new matrix-form iterative methods are presented to solve the least-squares problem:
\documentclass{article}\usepackage[mathscr]{euscript}\usepackage{amssymb,amsbsy,rotating}\footskip=0pc\pagestyle{empty}\begin{document}\[ \min\limits_{X\in {\mathscr{S}}_1,Y\in {\mathscr{S}}_2}\|AXB+CYD-E\| \]\end{document} and matrix nearness problem:\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\[ \min\limits_{[X: Y]\in S_{XY}}\|[X: Y]-[\widetilde{X}:\widetilde{Y}]\| \] \end{document} where matrices$A\in R^{p\times n_1},B\in R^{n_2\times q},C\in R^{p\times m_1},D\in R^{m_2\times q},E\in R^{p\times q},\widetilde{X}\in R^{n_1\times n_2}$ and$\widetilde{Y}\in R^{m_1\times m_2}$ are given; 𝒮1 and 𝒮2 are the set of constraint matrices, such as symmetric, skew symmetric, bisymmetric and centrosymmetric matrices sets and SXY is the solution pair set of the minimum residual problem. These new matrix-form iterative methods have also faster convergence rate and higher accuracy than the matrix-form iterative methods proposed by Peng and Peng (Numer. Linear Algebra Appl. 2006; 13: 473–485) for solving the linear matrix equation AXB+CYD=E. Paige's algorithms, which are based on the bidiagonalization procedure of Golub and Kahan, are used as the framework for deriving these new matrix-form iterative methods. Some numerical examples illustrate the efficiency of the new matrix-form iterative methods. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2008
- Full Text
- View/download PDF
26. Fast algorithms for designing variable FIR notch filters.
- Author
-
Routray, Aurobinda and Swain, Smarak
- Subjects
ALGORITHMS ,AUTOCORRELATION (Statistics) ,TOEPLITZ matrices ,MATHEMATICAL optimization ,MATRICES (Mathematics) - Abstract
The paper presents fast algorithms for designing finite impulse response (FIR) notch filters. The aim is to design a digital FIR notch filter so that the magnitude of the filter has a deep notch at a specified frequency, and as the notch frequency changes, the filter coefficients should be able to track the notch fast in real time. The filter design problem is first converted into a convex optimization problem in the autocorrelation domain. The frequency response of the autocorrelation of the filter impulse response is compared with the desired filter response and the integral square error is minimized with respect to the unknown autocorrelation coefficients. Spectral factorization is used to calculate the coefficients of the filter. In the optimization process, the computational advantage is obtained by exploiting the structure of the Hessian matrix which consists of a Toeplitz plus a Hankel matrix. Two methods have been used for solving the Toeplitz-plus-Hankel system of equations. In the first method, the computational time is reduced by using Block–Levinson's recursion for solving the Toeplitz-plus-Hankel system of matrices. In the second method, the conjugate gradient method with different preconditioners is used to solve the system. Comparative studies demonstrate the computational advantages of the latter. Both these algorithms have been used to obtain the autocorrelation coefficients of notch filters with different orders. The original filter coefficients are found by spectral factorization and each of these filters have been tested for filtering synthetic as well as real-life signals. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
27. Kronecker product approximations for dense block Toeplitz-plus-Hankel matrices.
- Author
-
Kilmer, M. E. and Nagy, J. G.
- Subjects
KRONECKER products ,MATRICES (Mathematics) ,FACTORIZATION ,IMAGE processing ,ALGORITHMS - Abstract
In this paper, we consider the approximation of dense block Toeplitz-plus-Hankel matrices by sums of Kronecker products of Toeplitz-plus-Hankel matrices. We present an algorithm for efficiently computing the matrix approximation that requires the factorization of matrices of much smaller dimension than that of the original. The main results are described for block Toeplitz matrices with Toeplitz-plus-Hankel blocks, but the algorithms can be readily adjusted for other related structures that arise in image processing applications, such as block Toeplitz with Toeplitz blocks and block Toeplitz-plus-Hankel with Toeplitz-plus-Hankel blocks. Our work extends the techniques in Kamm and Nagy (SIAM J. Matrix Anal. Appl. 2000; 22:155–172) and Nagy et al. (SIAM J. Matrix Anal. Appl. 2004; 25:829–841), which consider similar matrices, but with the added restriction that the matrices have a banded/block-banded structure. We illustrate the effectiveness of our algorithm by using the output of the algorithm to construct preconditioners for systems from two different applications: diffuse optical tomography and atmospheric image deblurring. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
28. A Rayleigh quotient minimization algorithm based on algebraic multigrid.
- Author
-
Hetmaniuk, U.
- Subjects
ALGORITHMS ,ALGEBRA ,MATRICES (Mathematics) ,RAYLEIGH quotient ,GEOMETRY - Abstract
This paper presents a new algebraic extension of the Rayleigh quotient multigrid (RQMG) minimization algorithm to compute the smallest eigenpairs of a symmetric positive definite pencil (A, M). Earlier versions of RQMG minimize the Rayleigh quotient over a hierarchy of geometric grids. We replace the geometric mesh information with the algebraic information defined by an algebraic multigrid preconditioner. At each level, we minimize the Rayleigh quotient with a block preconditioned algorithm. Numerical experiments illustrate the efficiency of this new algorithm to compute several eigenpairs. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
29. Analysis of block matrix preconditioners for elliptic optimal control problems.
- Author
-
Mathew, T. P., Sarkis, M., and Schaerer, C. E.
- Subjects
MATRICES (Mathematics) ,ALGORITHMS ,OPERATIONS research ,LINEAR differential equations ,BOUNDARY value problems ,METHODOLOGY - Abstract
In this paper, we describe and analyse several block matrix iterative algorithms for solving a saddle point linear system arising from the discretization of a linear-quadratic elliptic control problem with Neumann boundary conditions. To ensure that the problem is well posed, a regularization term with a parameter α is included. The first algorithm reduces the saddle point system to a symmetric positive definite Schur complement system for the control variable and employs conjugate gradient (CG) acceleration, however, double iteration is required (except in special cases). A preconditioner yielding a rate of convergence independent of the mesh size h is described for Ω ⊂ R
2 or R3 , and a preconditioner independent of h and α when Ω ⊂ R2 . Next, two algorithms avoiding double iteration are described using an augmented Lagrangian formulation. One of these algorithms solves the augmented saddle point system employing MINRES acceleration, while the other solves a symmetric positive definite reformulation of the augmented saddle point system employing CG acceleration. For both algorithms, a symmetric positive definite preconditioner is described yielding a rate of convergence independent of h. In addition to the above algorithms, two heuristic algorithms are described, one a projected CG algorithm, and the other an indefinite block matrix preconditioner employing GMRES acceleration. Rigorous convergence results, however, are not known for the heuristic algorithms. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2007
- Full Text
- View/download PDF
30. Direct algorithms to solve the two-sided obstacle problem for an M-matrix.
- Author
-
Zeng, J. P. and Jiang, Y. J.
- Subjects
ALGORITHMS ,MATRICES (Mathematics) ,COMPUTATIONAL complexity ,POLYNOMIALS ,ALGEBRA ,MATHEMATICS - Abstract
In this paper, two direct algorithms for solving the two-sided obstacle problem with an M-matrix are presented. The algorithms are well defined and have polynomial computational complexity. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
31. Kronecker product approximations for image restoration with anti-reflective boundary conditions.
- Author
-
Perrone, Lisa
- Subjects
IMAGE reconstruction ,MATRICES (Mathematics) ,KRONECKER products ,ALGORITHMS ,BOUNDARY value problems ,SYMMETRIC matrices ,ABSTRACT algebra - Abstract
The anti-reflective boundary condition for image restoration was recently introduced as a mathematically desirable alternative to other boundary conditions presently represented in the literature. It has been shown that, given a centrally symmetric point spread function (PSF), this boundary condition gives rise to a structured blurring matrix, a submatrix of which can be diagonalized by the discrete sine transform (DST), leading to an O(n
2 log n) solution algorithm for an image of size n × n. In this paper, we obtain a Kronecker product approximation of the general structured blurring matrix that arises under this boundary condition, regardless of symmetry properties of the PSF. We then demonstrate the usefulness and efficiency of our approximation in an SVD-based restoration algorithm, the computational cost of which would otherwise be prohibitive. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2006
- Full Text
- View/download PDF
32. Ordering techniques for singly bordered block diagonal forms for unsymmetric parallel sparse direct solvers.
- Author
-
Yifan Hu and Scott, Jennifer
- Subjects
LINEAR systems ,SPARSE matrices ,MATRICES (Mathematics) ,EQUATIONS ,ALGORITHMS ,FACTORIZATION ,MATHEMATICS ,VERTEX detectors - Abstract
The solution of large sparse linear systems of equations is one of the cornerstones of scientific computation. In many applications it is important to be able to solve these systems as rapidly as possible. One approach for very large problems is to reorder the system matrix to bordered block diagonal form and then to solve the block system using a coarse-grained parallel approach. In this paper, we consider the problem of efficiently ordering unsymmetric systems to singly bordered block diagonal form. Algorithms such as the MONET algorithm of Hu et al. (Comput. Chem. Eng. 23 (2000) 1631) that depend upon computing a representation of AA
T can be prohibitively expensive when a single (or small number of) matrix factorizations are required. We therefore work with the graph of AT + A (or BT + B, where B is a row permutation of A) and propose new reordering algorithms that use only vertex separators and wide separators of this graph. Numerical experiments demonstrate that our methods are efficient and can produce bordered forms that are competitive with those obtained using MONET. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
33. A pivoting strategy for symmetric tridiagonal matrices.
- Author
-
Bunch, James R. and Marcia, Roummel F.
- Subjects
FACTORIZATION ,LINEAR systems ,MATRICES (Mathematics) ,MAGNITUDE estimation ,ALGORITHMS ,COPYRIGHT - Abstract
The LBL
T factorization of Bunch for solving linear systems involving a symmetric indefinite tridiagonal matrix T is a stable, efficient method. It computes a unit lower triangular matrix L and a block 1 × 1 and 2 × 2 matrix B such that T=LBLT . Choosing the pivot size requires knowing a priori the largest element σ of T in magnitude. In some applications, it is required to factor T as it is formed without necessarily knowing σ. In this paper, we present a modification of the Bunch algorithm that can satisfy this requirement. We demonstrate that this modification exhibits the same bound on the growth factor as the Bunch algorithm and is likewise normwise backward stable. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
34. Low-complexity minimization algorithms.
- Author
-
Di Fiore, Carmine, Fanelli, Stefano, and Zellini, Paolo
- Subjects
ALGORITHMS ,ALGEBRA ,MATRICES (Mathematics) ,ABSTRACT algebra ,UNIVERSAL algebra ,MATHEMATICS - Abstract
Structured matrix algebras ℒ and a generalized BFGS-type iterative scheme have been recently investigated to introduce low-complexity quasi-Newton methods, named ℒQN, for solving general (non-structured) minimization problems. In this paper we introduce the ℒ
k QN methods, which exploit ad hoc algebras at each step. Since the structure of the updated matrices can be modified at each iteration, the new methods can better fit the Hessian matrix, thereby improving the rate of convergence of the algorithm. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
35. An implicit QR algorithm for symmetric semiseparable matrices.
- Author
-
Vandebril, Raf, Van Barel, Marc, and Mastronardi, Nicola
- Subjects
MATRICES (Mathematics) ,EIGENVALUES ,EIGENVECTORS ,VECTOR spaces ,COMPUTER algorithms ,ALGORITHMS - Abstract
The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n
3 ) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
36. Preconditioning strategies for non-Hermitian Toeplitz linear systems.
- Author
-
Huckle, Thomas, Serra-Capizzano, Stefano, and Tablino-Possio, Cristina
- Subjects
TOEPLITZ matrices ,MATRICES (Mathematics) ,GENERATING functions ,COMBINATORICS ,HERMITIAN forms ,ALGORITHMS - Abstract
In this paper, we propose and analyse preconditioning strategies for non-Hermitian Toeplitz linear systems. These techniques used in connection with the GMRES algorithm allow to solve in an optimal way the corresponding linear systems. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
37. On computing minimal realizable spectral radii of non-negative matrices.
- Author
-
Chu, Moody T. and Shu-Fang Xu
- Subjects
EIGENVALUES ,MATRICES (Mathematics) ,ALGEBRA ,SPECTRAL geometry ,ALGORITHMS ,SPECTRUM analysis - Abstract
For decades considerable efforts have been exerted to resolve the inverse eigenvalue problem for non-negative matrices. Yet fundamental issues such as the theory of existence and the practice of computation remain open. Recently, it has been proved that, given an arbitrary (n–1)-tuple ℒ = (λ
2 ,...,λn ) ∈ ℂn–1 whose components are closed under complex conjugation, there exists a unique positive real number ℛ(ℒ), called the minimal realizable spectral radius of ℒ, such that the set {λ1 ,...,λn } is precisely the spectrum of a certain n × n non-negative matrix with λ1 as its spectral radius if and only if λ1 ⩾ ℛ(ℒ). Employing any existing necessary conditions as a mode of checking criteria, this paper proposes a simple bisection procedure to approximate the location of ℛ(ℒ). As an immediate application, it offers a quick numerical way to check whether a given n-tuple could be the spectrum of a certain non-negative matrix. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
38. Structured weighted low rank approximation.
- Author
-
Schuermans, M., Lemmerling, P., and Van Huffel, S.
- Subjects
APPROXIMATION theory ,HANKEL functions ,MATRICES (Mathematics) ,MATHEMATICAL optimization ,ALGORITHMS - Abstract
This paper extends the weighted low rank approximation (WLRA) approach towards linearly structured matrices. In the case of Hankel matrices an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. The correctness of the latter algorithm is verified on a benchmark problem. Finally the statistical accuracy and numerical efficiency of the proposed algorithm is compared with that of STLNB, a previously proposed algorithm for solving Hankel WLRA problems. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
39. An algebraic preconditioning method for M-matrices: linear versus non-linear multilevel iteration.
- Author
-
Kraus, J.K.
- Subjects
MATRICES (Mathematics) ,FACTORIZATION ,ALGORITHMS ,ALGEBRA ,LINEAR algebra ,ABSTRACT algebra - Abstract
In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non-linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W-cycles only need diagonal solvers on all levels and additionally evaluate a second-degree matrix polynomial (linear case), or, perform ν inner GCG-type iterations (non-linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non-linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non-linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured-grid problems. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
40. Sparse matrix element topology with application to AMG(e) and preconditioning<FNR></FNR><FN>This article is a US Government work and is in the public domain in the USA </FN>.
- Author
-
Vassilevski, Panayot S.
- Subjects
TOPOLOGY ,MATRICES (Mathematics) ,MULTIGRID methods (Numerical analysis) ,NUMERICAL analysis ,ALGEBRA ,ALGORITHMS - Abstract
This paper defines topology relations of elements treated as overlapping lists of nodes. In particular, the element topology makes use of element faces, element vertices and boundary faces which coincide with the actual (geometrical) faces, vertices and boundary faces in the case of true finite elements. The element topology is used in an agglomeration algorithm to produce agglomerated elements (a non-overlapping partition of the original elements) and their topology is then constructed, thus allowing for recursion. The main part of the algorithms is based on operations on Boolean sparse matrices and the implementation of the algorithms can utilize any available (parallel) sparse matrix format. Applications of the sparse matrix element topology to AMGe (algebraic multigrid for finite element problems), including elementwise constructions of coarse non-linear finite element operators are outlined. An algorithm to generate a block nested dissection ordering of the nodes for generally unstructured finite element meshes is given as well. The coarsening of the element topology is illustrated on a number of fine-grid unstructured triangular meshes. Published in 2002 by John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
41. Stable factorization for Hankel and Hankel-like matrices.
- Author
-
Olshevsky, Vadim and Stewart, Michael
- Subjects
FACTORIZATION ,MATRICES (Mathematics) ,LINEAR algebra ,ALGORITHMS ,ERROR analysis in mathematics ,MATHEMATICAL statistics - Abstract
This paper gives fast O(n
2 ) algorithms for the factorization of positive-definite and indefinite Hankel matrices. The algorithms are based on the concept of displacement structure and are valid for the more general class of Hankel-like matrices. The positive-definite algorithm is proven to be backward stable. The indefinite algorithm uses a look-ahead step that is naturally suggested by displacement approach. Our error analysis suggests a new criterion for the size of the look-ahead step and our numerical experiments suggest that the use of the new criterion allows us to ensure numerical stability in practice. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2001
- Full Text
- View/download PDF
42. An incomplete LU-factorization algorithm based on block bordering.
- Author
-
Kolotilina, L. Yu., Nikishin, A.A., and Yeremin, A. Yu.
- Subjects
ALGORITHMS ,FACTORIZATION ,MATRICES (Mathematics) ,INVERSE functions ,APPROXIMATION theory ,SYMMETRIC functions - Abstract
This paper suggests a new algorithm, called IBBLU, for constructing incomplete LU-factorizations of general non-singular sparse matrices. This algorithm is based on the block bordering idea and uses factorized sparse approximate inverses to approximate the inverses of pivot blocks. The triangular factors L and U are represented in explicit-implicit block form, which enhances the flop performance of the preconditioning. The algorithm suggested is theoretically justified for M- and H-matrices, and its competitiveness with the best available algebraic preconditioning methods in both symmetric and unsymmetric cases is demonstrated numerically. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
43. Editorial.
- Author
-
Axelsson, Owe
- Subjects
PERIODICALS ,LINEAR algebra ,ALGORITHMS ,MATHEMATICAL models ,EIGENVALUES ,MATRICES (Mathematics) ,PARTIAL differential equations - Abstract
This is a new international journal "Numerical Linear Algebra With Applications," which publishes refereed papers describing significant developments in numerical linear algebra and the application of such method; to the solution of practical problems, such as occur in engineering, for instance. Numerical linear algebra algorithms form the core of almost any solution algorithm found in mathematical modeling. The models originate in physics, chemistry, engineering, ecology, economy and social sciences. Frequently they involve solutions of systems of algebraic equations and eigenvalue problems derived by some discretization method used for partial differential equations.
- Published
- 1994
- Full Text
- View/download PDF
44. Optimal v-cycle algebraic multilevel preconditioning.
- Author
-
Notay, Yvan
- Subjects
ALGEBRA ,FACTORIZATION ,MATHEMATICS ,SCHUR functions ,MATRICES (Mathematics) ,ALGORITHMS - Abstract
We consider algebraic multilevel preconditioning methods based on the recursive use of a 2 × 2 block incomplete factorization procedure in which the Schur complement is approximated by a coarse grid matrix. As is well known, for discrete second-order elliptic PDEs, optimal convergence properties are proved for such basic two-level schemes under mild assumptions on the PDE coefficients, but their recursive use in a simple V-cycle algorithm does not generally lead to optimal order convergence. In the present paper, we analyse the combination of these techniques with a smoothing procedure much the same as the one used in standard multigrid algorithms, except that smoothing is not required on the finest grid. Theoretical results prove optimal convergence properties for the V-cycle under an assumption similar to the ‘approximation property’ of the classical multigrid convergence theory. On the other hand, numerical experiments made on both 2D and 3D problems show that the condition number is close to that of the two-level method. Further, the method appears robust in the presence of discontinuity and anisotropy, even when the material interfaces are not aligned with the coarse grid. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 1998
- Full Text
- View/download PDF
45. Implicit Cholesky Algorithms for Singular Values and Vectors of Triangular Matrices.
- Author
-
Fernando, K. Vince and Parlett, Beresford N.
- Subjects
ALGORITHMS ,ALGEBRA ,MATRICES (Mathematics) ,EIGENVALUES ,NOISE generators (Electronics) ,JACOBI method - Abstract
The implicit Cholesky algorithm has been developed by several authors during the last 10 years but under different names. We identify the algorithm with a special version of Rutishauser's LR algorithm. Intermediate quantities in the transformation furnish several attractive approximations to the smallest singular value. The paper extols the advantages of using shifts with the algorithm. The nonorthogonal transformations improve accuracy. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
46. The RSCG Algorithm on Distributed Memory Architectures.
- Author
-
Freitag, Lori and Ortega, James
- Subjects
CONJUGATE gradient methods ,DISTRIBUTED computing ,MATHEMATICAL decomposition ,ALGORITHMS ,MATRICES (Mathematics) ,ALGEBRA ,BOUNDARY value problems ,COMPUTER algorithms ,NUMERICAL solutions to equations ,DIRICHLET problem ,MATHEMATICAL analysis - Abstract
In this paper, we demonstrate the scalability of the Reduced System Conjugate Gradient (RSCG) algorithm on distributed memory architectures. We present speed-up results obtained on the Intel iPSC/860 that compare one-, two-, and three-dimensional decompositions of the domain lot both positive definite and positive semidefinite test problems. We develop a model for the RSCG algorithm to analyze computational and communication costs. The model is validated using experimental data and then used to examine and predict behavior of the RSCG algorithm as a function of architecture parameters including communication latency and transmission times and memory access costs. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
47. Progress in the Numerical Solution of the Nonsymmetric Eigenvalue Problem.
- Author
-
Zhaojun Bai, Leonid
- Subjects
MATRICES (Mathematics) ,ABSTRACT algebra ,SPARSE matrices ,CATALECTICANT matrices ,ENGINEERING ,ALGORITHMS - Abstract
With the growing demands from disciplinary and interdisciplinary fields of science and engineering for the numerical solution of the nonsymmetric eigenvalue problem, competitive new techniques have been developed for solving the problem. In this paper we examine the state of the art of the algorithmic techniques and the software scene for the problem. Some current developments are also outlined. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
48. Matrix Shapes Invariant under the Symmetric QR Algorithm.
- Author
-
Arbenz, Peter and Golub, Gene H.
- Subjects
EIGENVALUES ,MATRICES (Mathematics) ,ALGORITHMS ,ABSTRACT algebra ,FOUNDATIONS of arithmetic ,JACOBI method - Abstract
The OR algorithm is a basic algorithm for computing the eigenvalues of dense matrices. For efficiency reasons it is prerequisite that the algorithm is applied only after the original matrix has been reduced to a matrix of a particular shape, most notably Hessenberg and tridiagonal, which is preserved during the iterative process. In certain circumstances a reduction to another matrix shape may be advantageous. In this paper, we identify which zero patterns of symmetric matrices are preserved under the OR algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
49. Algebraic Multilevel Iteration Method for Stieltjes Matrices.
- Author
-
Axelsson, O. and Neytcheva, M.
- Subjects
ALGEBRAIC functions ,CHEBYSHEV polynomials ,ORTHOGONAL polynomials ,CHEBYSHEV systems ,MATRICES (Mathematics) ,FINITE element method ,ALGORITHMS - Abstract
The numerical solution of elliptic selfadjoint second-order boundary value problems leads to a class of linear systems of equations with symmetric, positive definite, large and sparse matrices which can be solved iteratively using a preconditioned version of some algorithm. Such differential equations originate from various applications such as heat conducting and electromagnetics. Systems of equations of similar type can also arise in the finite element analysis of structures. We discuss a recursive method constructing preconditioners to a symmetric, positive definite matrix. An algebraic multilevel technique based on partitioning of the matrix in two by two matrix block form, approximating some of these by other matrices with more simple sparsity structure and using the corresponding Schur complement as a matrix on the lower level, is considered. The quality of the preconditioners is improved by special matrix polynomials which recursively connect the preconditioners on every two adjoining levels. Upper and lower bounds for the degree of the polynomials are derived as conditions for a computational complexity of optimal order for each level and for an optimal rate of convergence, respectively. The method is an extended and more accurate algebraic formulation of a method for nine-point and mixed five- and nine-point difference matrices, presented in some previous papers. [ABSTRACT FROM AUTHOR]
- Published
- 1994
- Full Text
- View/download PDF
50. Sampling and multilevel coarsening algorithms for fast matrix approximations.
- Author
-
Ubaru, Shashanka and Saad, Yousef
- Subjects
SINGULAR value decomposition ,ALGORITHMS ,SUBSET selection ,APPROXIMATION error ,MATRICES (Mathematics) ,REPRESENTATIONS of graphs - Abstract
Summary: This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low‐rank approximation method used in data‐related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.