检索结果-内蒙古大学图书馆

A superfast algorithm for toeplitz systems of linear equations

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2007年第4期29卷 1247-1266页

作者： Chandrasekaran, S. Gu, M. Sun, X. Xia, J. Zhu, J. Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Univ Calif Berkeley Dept Mech Engn Berkeley CA 94720 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

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.

关键词： displacement equation SSS structure superfast algorithm Toeplitz matrix

来源：评论

学校读者我要写书评

暂无评论

IMPLEMENTATION OF A superfast algorithm FOR SYMMETRIC POSITIVE DEFINITE LINEAR EQUATIONS OF DISPLACEMENT RANK-2

IMPLEMENTATION OF A SUPERFAST ALGORITHM FOR SYMMETRIC POSITI...

引用

5th SPIE Conference on Advanced Signal Processing - algorithms, Architectures, and Implementations

作者： HUCKLE, T UNIV WURZBURG INST ANGEW MATHD-97074 WURZBURGGERMANY

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)² 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.

关键词： DISPLACEMENT RANK superfast algorithm TOEPLITZ MATRIX

来源：评论

学校读者我要写书评

暂无评论

A superfast Randomized algorithm to Decompose Binary Forms 16

A Superfast Randomized Algorithm to Decompose Binary Forms

引用

41st ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Bender, Matias R. Faugere, Jean-Charles Ferret, Ludovic Tsigaridas, Elias Univ Paris 06 Sorbonne Univ CNRS Equipe POLSYSINRIALIP6 4 Pl Jussieu F-75252 Paris 05 France

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.

关键词： Binary Form Decomposition superfast algorithm Hankel Matrix Complexity Algebraic Degree Canonical Form Waring's problem

来源：评论

学校读者我要写书评

暂无评论

A DIVIDE AND CONQUER algorithm FOR THE superfast SOLUTION OF TOEPLITZ-LIKE SYSTEMS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2012年第4期33卷 1039-1056页

作者： Favati, Paola Lotti, Grazia Menchi, Ornella CNR IIT I-56124 Pisa Italy Univ Parma Dept Math I-43100 Parma Italy Univ Pisa Dipartment Comp Sci I-56127 Pisa Italy

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.

关键词： divide and conquer algorithm superfast algorithm Toeplitz-like matrices

来源：评论

学校读者我要写书评

暂无评论

Generalization of superfast LayerPeeling Methods to the Manakov System

引用

MOSCOW UNIVERSITY PHYSICS BULLETIN 2022年第1期77卷 23-30页

作者： Dolmatov, A. S. Konyaev, D. A. Lomonosov Moscow State Univ Moscow 119991 Russia

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.

关键词： fiber-optic communication superfast algorithm Manakov system of equations

来源：评论

学校读者我要写书评

暂无评论

A superfast solver for real symmetric Toeplitz systems using real trigonometric transformations

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2005年第8期12卷 699-713页

作者： Codevico, G Heinig, G Van Barel, M Katholieke Univ Leuven Dept Comp Sci B-3001 Louvain Belgium Kuwait Univ Dept Math & Comp Sci Safat 13060 Kuwait

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.

关键词： symmetric Toeplitz matrix superfast algorithm tangential interpolation cosine and sine transform

来源：评论

学校读者我要写书评

暂无评论

A superfast method for solving Toeplitz linear least squares problems

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2003年第0期366卷 441-457页

作者： Van Barel, M Heinig, G Kravanja, P Katholieke Univ Leuven Dept Comp Sci B-3001 Heverlee Belgium Kuwait Univ Dept Math & Comp Sci Safat 13060 Kuwait

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.

关键词： least squares problem Toeplitz matrices structured matrices superfast algorithm block circulant matrices vector polynomial interpolation divide and conquer strategy

来源：评论

学校读者我要写书评

暂无评论

A superfast method for solving Toeplitz linear least squares problems

A superfast method for solving Toeplitz linear least squares...

引用

作者： Van Barel, Marc Heinig, Georg Kravanja, Peter Department of Computer Science Katholieke Universiteit Leuven Celestijnenlaan 200 A B-3001 Heverlee Belgium Department of Mathematics and Computer Science Kuwait University P.O. Box 5969 Safat 13060 Kuwait

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. 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. © 2003 Elsevier Science Inc.

关键词： Block circulant matrices Divide and conquer strategy Least squares problem Structured matrices superfast algorithm Toeplitz matrices Vector polynomial interpolation

来源：评论

学校读者我要写书评

暂无评论

Wiener-Hopf and spectral factorization of real polynomials by Newton's method

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2013年第12期438卷 4760-4805页

作者： Boettcher, Albrecht Halwass, Martin TU Chemnitz Fac Math D-09107 Chemnitz Germany

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.

关键词： Wiener-Hopf factorization Spectral factorization Polynomial factorization Newton's method Structured matrices Fast algorithm superfast algorithm

来源：评论

学校读者我要写书评

暂无评论

Mapping computations

引用

JOURNAL OF SUPERCOMPUTING 2009年第2期48卷 152-162页

作者： Chen, Zhao New York City Coll Technol Dept Math Brooklyn NY 11201 USA

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).

关键词： Structure matrices Matrix-vector product Kronecker-like matrices superfast algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：