Home About us Contact
|
Home About us Contact | ||
|
|
||
Toeplitz Matrices (toeplitz + matrix)
Selected AbstractsA parallel Broyden approach to the Toeplitz inverse eigenproblemCONCURRENCY AND COMPUTATION: PRACTICE & EXPERIENCE, Issue 6 2004Jesús Peinado Abstract In this work we show a portable sequential and a portable parallel algorithm for solving the inverse eigenproblem for real symmetric Toeplitz matrices. Both algorithms are based on Broyden's method for solving nonlinear systems. We reduced the computational cost for some problem sizes, and furthermore we managed to reduce spatial cost considerably, compared in both cases with parallel algorithms proposed by other authors and by us, although sometimes quasi-Newton methods (as Broyden) do not reach convergence in all the test cases. We have implemented the parallel algorithm using the parallel numerical linear algebra library SCALAPACK based on the MPI environment. Experimental results have been obtained using two different architectures: a shared memory multiprocessor, the SGI PowerChallenge, and a cluster of Pentium II PCs connected through a myrinet network. The algorithms obtained are scalable in all the cases. Copyright © 2004 John Wiley & Sons, Ltd. [source] An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matricesNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 2-3 2010M. Donatelli Abstract Local Fourier analysis (LFA) is a classical tool for proving convergence theorems for multigrid methods (MGMs). In particular, we are interested in optimal convergence, i.e. convergence rates that are independent of the problem size. For elliptic partial differential equations (PDEs), a well-known optimality result requires that the sum of the orders of the grid transfer operators is not lower than the order of the PDE approximated. Analogously, when dealing with MGMs for Toeplitz matrices, a well-known optimality condition concerns the position and the order of the zeros of the symbols of the grid transfer operators. In this work we show that in the case of elliptic PDEs with constant coefficients, the two different approaches lead to an equivalent condition. We argue that the analysis for Toeplitz matrices is an algebraic generalization of the LFA, which allows to deal not only with differential problems but also for instance with integral problems. The equivalence of the two approaches gives the possibility of using grid transfer operators with different orders also for MGMs for Toeplitz matrices. We give also a class of grid transfer operators related to the B-spline's refinement equation and study their geometric properties. Numerical experiments confirm the correctness of the proposed analysis. Copyright © 2010 John Wiley & Sons, Ltd. [source] Preconditioners for ill-posed Toeplitz matrices with differentiable generating functionsNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 3 2009C. Estatico Abstract Both theoretical analysis and numerical experiments in the literature have shown that the Tyrtyshnikov circulant superoptimal preconditioner for Toeplitz systems can speed up the convergence of iterative methods without amplifying the noise of the data. Here we study a family of Tyrtyshnikov-based preconditioners for discrete ill-posed Toeplitz systems with differentiable generating functions. In particular, we show that the distribution of the eigenvalues of these preconditioners has good regularization features, since the smallest eigenvalues stay well separated from zero. Some numerical results confirm the regularization effectiveness of this family of preconditioners. Copyright © 2009 John Wiley & Sons, Ltd. [source] A fast algorithm for computing the smallest eigenvalue of a symmetric positive-definite Toeplitz matrixNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 4 2008N. Mastronardi Abstract Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive-definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R,1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd. [source] Asymptotic properties of the QR factorization of banded Hessenberg,Toeplitz matricesNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 7 2005Xiao-Wen Chang Abstract We consider Givens QR factorization of banded Hessenberg,Toeplitz matrices of large order and relatively small bandwidth. We investigate the asymptotic behaviour of the R factor and Givens rotation when the order of the matrix goes to infinity, and present some interesting convergence properties. These properties can lead to savings in the computation of the exact QR factorization and give insight into the approximate QR factorizations of interest in preconditioning. The properties also reveal the relation between the limit of the main diagonal elements of R and the largest absolute root of a polynomial. Copyright © 2005 John Wiley & Sons, Ltd. [source] Structured condition numbers of large Toeplitz matrices are rarely better than usual condition numbersNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 2-3 2005A. Böttcher Abstract When working with structured matrices, structured condition numbers are more meaningful than usual condition numbers. The usual condition numbers of Toeplitz matrices may grow exponentially with the dimension of the matrix. The purpose of this note is to show that in this case the structured condition numbers do with high probability also increase exponentially, which supports the claim that one is not likely to win much on the average Toeplitz input by passing from the usual condition numbers of Toeplitz matrices to their structured counterparts. Copyright © 2004 John Wiley & Sons, Ltd. [source] MGM Optimal convergence for certain (multilevel) structured linear systemsPROCEEDINGS IN APPLIED MATHEMATICS & MECHANICS, Issue 1 2003Antonio Aricó Dr. We present a multigrid algorithm to solve linear systems whose coefficient metrices belongs to circulant, Hartley or , multilevel algebras and are generated by a nonnegative multivariate polynomial f. It is known that these matrices are banded (with respect to their multilevel structure) and their eigenvalues are obtained by sampling f on uniform meshes, so they are ill-conditioned (or singular, and need some corrections) whenever f takes the zero value. We prove the proposed metod to be optimal even in presence of ill-conditioning: if the multilevel coefficient matrix has dimension ni at level i, i = 1, , , d, then only ni operations are required on each iteration, but the convergence rate keeps constant with respect to N(n) as it depends only on f. The algorithm can be extended to multilevel Toeplitz matrices too. [source] Wave packet pseudomodes of twisted Toeplitz matricesCOMMUNICATIONS ON PURE & APPLIED MATHEMATICS, Issue 9 2004Lloyd N. Trefethen The pseudospectra of banded, nonsymmetric Toeplitz or circulant matrices with varying coefficients are considered. Such matrices are characterized by a symbol that depends on both position (x) and wave number (k). It is shown that when a certain winding number or twist condition is satisfied, related to Hörmander's commutator condition for partial differential equations, ,-pseudoeigenvectors of such matrices for exponentially small values of , exist in the form of localized wave packets. The symbol need not be smooth with respect to x, just differentiable at a point (or less). © 2004 Wiley Periodicals, Inc. [source] Evaluating recursive filters on distributed memory parallel computersINTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN BIOMEDICAL ENGINEERING, Issue 11 2006Przemys, aw Stpiczy, skiArticle first published online: 6 APR 200 Abstract The aim of this paper is to show that the recently developed high performance divide and conquer algorithm for solving linear recurrence systems with constant coefficients together with the new BLAS-based algorithm for narrow-banded triangular Toeplitz matrix,vector multiplication, allow to evaluate linear recursive filters efficiently on distributed memory parallel computers. We apply the BSP model of parallel computing to predict the behaviour of the algorithm and to find the optimal values of the method's parameters. The results of experiments performed on a cluster of twelve dual-processor Itanium 2 computers and Cray X1 are also presented and discussed. The algorithm allows to utilize up to 30% of the peak performance of 24 Itanium processors, while a simple scalar algorithm can only utilize about 4% of the peak performance of a single processor. Copyright © 2006 John Wiley & Sons, Ltd. [source] A fast algorithm for computing the smallest eigenvalue of a symmetric positive-definite Toeplitz matrixNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 4 2008N. Mastronardi Abstract Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive-definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R,1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd. [source] Analysis of a circulant based preconditioner for a class of lower rank extracted systemsNUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, Issue 1 2005S. Salapaka Abstract This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, Apx=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. [source] | |||||||||||||