In this paper we develop a new superfast solver for Toeplitz systems of linear equations. To solve Toeplitz systems many people use displacement equation methods. With displacement structures, Toeplitz matrices can be...
详细信息
In this paper we develop a new superfast solver for Toeplitz systems of linear equations. To solve Toeplitz systems many people use displacement equation methods. With displacement structures, Toeplitz matrices can be transformed into Cauchy-like matrices using the FFT or other trigonometric transformations. These Cauchy-like matrices have a special property, that is, their off-diagonal blocks have small numerical ranks. This low-rank property plays a central role in our superfast Toeplitz solver. It enables us to quickly approximate the Cauchy-like matrices by structured matrices called sequentially semiseparable (SSS) matrices. The major work of the constructions of these SSS forms can be done in precomputations (independent of the Toeplitz matrix entries). These SSS representations are compact because of the low-rank property. The SSS Cauchy-like systems can be solved in linear time with linear storage. Excluding precomputations the main operations are the FFT and SSS system solve, which are both very efficient. Our new Toeplitz solver is stable in practice. Numerical examples are presented to illustrate the efficiency and the practical stability.
In this paper we describe the implementation and first numerical results for the superfast algorithm based on a modified version of the Bitmead/Anderson-algorithm for real symmetric positive definite matrices of displ...
详细信息
ISBN:
(纸本)0819416207
In this paper we describe the implementation and first numerical results for the superfast algorithm based on a modified version of the Bitmead/Anderson-algorithm for real symmetric positive definite matrices of displacement rank 2. The total number of arithmetic operations for this algorithm is of order 93.75 nlog(n)2 flops. The method is based on repeatedly dividing the original problem into two subproblems with leading principal submatrix and the related Schur complement. All occurring matrices are represented by generating vectors of their displacement rank characterization.
Symmetric Tensor Decomposition is a major problem that arises in areas such as signal processing, statistics, data analysis and computational neuroscience. It is equivalent to write a homogeneous polynomial in n varia...
详细信息
ISBN:
(纸本)9781450343800
Symmetric Tensor Decomposition is a major problem that arises in areas such as signal processing, statistics, data analysis and computational neuroscience. It is equivalent to write a homogeneous polynomial in n variables of degree D as a sum of D-th powers of linear forms, using the minimal number of summands. This minimal number is called the rank of the polynomial/tensor. We consider the decomposition of binary forms, that corresponds to the decomposition of symmetric tensors of dimension 2 and order D. This problem has its roots in Invariant Theory, where the decompositions are known as canonical forms. As part of that theory, different algorithms were proposed for the binary forms. In recent years, those algorithms were extended for the general symmetric tensor decomposition problem. We present a new randomized algorithm that enhances the previous approaches with results from structured linear algebra and techniques from linear recurrent sequences. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have quadratic complexity bounds. We compute a symbolic minimal decomposition in O(M(D)log(D)) arithmetic operations, where M(D) is the complexity of multiplying two polynomials of degree D. We approximate the terms of the decomposition with an error of 2, in O(D log(2) (D) (log(2) (D) log (epsilon))) arithmetic operations. To bound the size of the representation of the coefficients involved in the decomposition, we bound the algebraic degree of the problem by min(rank,D rank 1). When the input polynomial has integer coefficients, our algorithm performs, up to poly -logarithmic factors, (O) over tildeB(Dl+ D-4 D-3 tau) bit operations, where 2 is the maximum bitsize of the coefficients and 2ce is the relative error of the terms in the decomposition.
In this paper a new O(N log(3) N) solver for N x N Toeplitz-like systems, based on a divide and conquer technique, is presented. Similarly to the superfast algorithm MBA for the inversion of a Toeplitz-like matrix [R....
详细信息
In this paper a new O(N log(3) N) solver for N x N Toeplitz-like systems, based on a divide and conquer technique, is presented. Similarly to the superfast algorithm MBA for the inversion of a Toeplitz-like matrix [R. R. Bitmead and B. D. O. Anderson, Linear Algebra Appl., 34 (1980), pp. 103-116;M. Morf, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, 1980, pp. 954-959], it exploits the displacement properties. In order to avoid the well-known numerical instability of the explicit inversion, the new algorithm relies on the triangular factorization and back-substitution formula for the system seen as a 2x2 block system with blocks of half size. This idea is the one used in [M. Stewart, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 669-693] to improve the numerical stability of superfast methods based on the generalized Schur algorithm for positive definite Toeplitz matrices, but the algorithm we propose can be applied also to nonsymmetric Toeplitz-like systems. The stability of the algorithm is examined through numerical experiments.
In the practical design of fiber-optic communication lines, one important parameter is the computational complexity of the method that is used, since the speed and energy efficiency of the receiving device directly de...
详细信息
In the practical design of fiber-optic communication lines, one important parameter is the computational complexity of the method that is used, since the speed and energy efficiency of the receiving device directly depend on this parameter. From an engineering point of view, the methods should be comparable in speed with a linear equalizer, whose computational complexity is Theta(N log(2) N) operations, where N is the number of time grid nodes. The subject of this work is a generalization of superfast (Theta(N log(2)(2) N) arithmetic operations) LayerPeeling and InverseLayerPeeling methods developed for the nonlinear Schrodinger equation for the Manakov system of equations. In this paper the LayerPeeling family algorithms were generalized to the case of double polarization system governed by the Manakov system of equations.
A new superfast O(n log(2) n) complexity direct solver for real symmetric Toeplitz systems is presented. The algorithm is based on 1. the reduction to symmetric right-band sides, 2. a polynomial interpretation in term...
详细信息
A new superfast O(n log(2) n) complexity direct solver for real symmetric Toeplitz systems is presented. The algorithm is based on 1. the reduction to symmetric right-band sides, 2. a polynomial interpretation in terms of Chebyshev polynomials, 3. an inversion formula involving real trigonometric transformations and 4. an interpretation of the equations as a tangential interpolation problem. The tangential interpolation problem is solved via a divide and conquer strategy and fast DCT. Copyright (c) 2005 John Wiley & Sons, Ltd.
In this paper we develop a superfast O((m + n) log(2)(m + n)) complexity algorithm to solve a linear least squares problem with an m x n Toeplitz coefficient matrix. The algorithm is based on the augmented matrix appr...
详细信息
In this paper we develop a superfast O((m + n) log(2)(m + n)) complexity algorithm to solve a linear least squares problem with an m x n Toeplitz coefficient matrix. The algorithm is based on the augmented matrix approach. The augmented matrix is further extended to a block circulant matrix and DFT is applied. This leads to an equivalent tangential interpolation problem where the nodes are roots of unity. This interpolation problem can be solved by a divide and conquer strategy in a superfast way. To avoid breakdowns and to stabilize the algorithm pivoting is used and a technique is applied that selects "difficult" points and treats them separately. The effectiveness of the approach is demonstrated by several numerical examples. (C) 2003 Elsevier Science Inc. All rights reserved.
In this paper we develop a superfast O((m+n)log2(m+n)) complexity algorithm to solve a linear least squares problem with an m×n Toeplitz coefficient matrix. The algorithm is based on the augmented matrix approach...
详细信息
We present a new method for factoring a real polynomial into the product of two polynomials which have their zeros inside and outside the unit circle, respectively. The approach is based on solving a nonlinear system ...
详细信息
We present a new method for factoring a real polynomial into the product of two polynomials which have their zeros inside and outside the unit circle, respectively. The approach is based on solving a nonlinear system by Newton's method. The Jacobi matrix is a polynomial of a companion matrix and thus a Bezoutian times the inverse of a triangular Toeplitz matrix. After getting deeper understanding of the displacement structure of the Bezoutian, each Newton step can be reduced to a few applications of discrete Fourier or cosine transforms and the LU-decomposition of a conceived linear system with a Cauchy-like matrix. These structural features are employed to design a fast algorithm, which shows excellent numerical behavior. For example, in the case of the extremely ill-conditioned test polynomial (2z(n) + Sigma(n-1)(k=0)z(k))(2 + Sigma(n)(k=1) z(k)) of the degree 2n = 20000, we obtain the factorization after 22 Newton steps with an error of 3.4-10(-8) in the Euclidean norm, the execution time on a laptop being a couple of minutes. The local quadratic convergence of our Newton method is proved and explicit convergence balls are given on the basis of estimates for the Lipschitz constant which occurs in Kantorovich's theorem. We also design and test two superfast versions of our method, which, for polynomials of degree 20000, typically need about half a minute to produce an initial coefficient vector and then perform the Newton iteration within one second. (C) 2013 Elsevier Inc. All rights reserved.
Let Z be a set of integers and Z(nxn) be a ring for any integer n. We define (s) over cap is an element of Z(n) as a latter point. Hom(Z(n), Z(m)) denotes as a homomorphism of Z(n) into Z(m). For any element (q) over ...
详细信息
Let Z be a set of integers and Z(nxn) be a ring for any integer n. We define (s) over cap is an element of Z(n) as a latter point. Hom(Z(n), Z(m)) denotes as a homomorphism of Z(n) into Z(m). For any element (q) over cap in Z(n), we define S + T : Z(n) -> Z(m) as (S + T)((q) over cap) = S((q) over cap) + T ((q) over cap). As a result, S + T become a homomorphism of Z(n) into Z(m). We also define kU : Z(n) -> Z(m) as (kU)((q) over cap) = k(U((q) over cap)). Consequently, kU become a homomorphism of Z(n) into Z(m). Moreover, Hom(Z(n), Z(m)) is isomorphic to Z(nxm). A novel class of the structured matrices which is a set of elements of Hom(Z(n), Z(n)) over a ring of integers with a displacement structure, referred to as a C-Cauchy-like matrix, will be formulated and presented. Using the displacement approach, which was originally discovered by Kailath, Kung, and Morf (J. Math. Anal. Appl. 68: 395-407, 1979), a new superfast algorithm for the multiplication of a C-Cauchy-like matrix of the size n x n over a field with a vector will be designed. The memory space for storing a C-Cauchy-like matrix of the size n x n over a field is O(n) versus O(n(2)) for a general matrix of the size n x n over a field. The arithmetic operations of a product of a C-Cauchy-like matrix and a vector is reduced dramatically to O(n) from O(n(2)), which can be used to transform a latter point (s) over cap is an element of Z(n) to another latter point (t) over cap is an element of Z(n) such that (t) over cap = C (s) over cap. Moreover, the displacement structure can also be extended to a Kronecker matrix W circle times Z. A new class of the Kronecker-like matrices with the displacement rank r, r < n will be also discovered. The memory space for storing a Kronecker-like matrix of the size (n x 1) circle times ( 1 x n) over a field is decreased to O(rn). The arithmetic operations for a product of a Kronecker-like matrix with the displacement rank r and a vector is also accelerated to O(rn).
暂无评论