COMPLEXITY OF MULTIPLICATION WITH VECTORS FOR STRUCTURED MATRICES

被引：72
作者：
GOHBERG, I
OLSHEVSKY, V
机构：
[1] School of Mathematical Sciences Raymond, Beverly Sackler Faculty, Exact Sciences Tel Aviv University Ramat Aviv
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 1994年 / 202卷
关键词：
D O I：
10.1016/0024-3795(94)90189-9
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Fast algorithms for computing the product with a vector are presented for a number of classes of matrices whose properties relate to the properties of Toeplitz, Vandermonde, or Cauchy matrices (these matrices are defined using the concept of displacement of a matrix) and also for their inverses. All the actions which are not dependent upon the coordinates of the input vector are singled out in a separate preprocessing stage. The proposed algorithms are based on new representations of these matrices, involving factor circulants.
引用
收藏
页码：163 / 192
页数：30
相关论文
共 16 条
[1]  
Aho A., 1976, DESIGN ANAL COMPUTER
[2]  
AMMAR G, 1990, SIGNAL PROCESSING SC, V3, P421
[3]  
Brent R.P., 1980, J ALGORITHMS, V1, P259
[4]   ALGEBRAIC COMPUTATIONS OF SCALED PADE FRACTIONS [J].
CABAY, S ;
CHOI, DK .
SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :243-270
[5]  
CANNY JF, 1989, 1989 P ACM SIGSAM IN, P34
[6]   DIVIDE-AND-CONQUER SOLUTIONS OF LEAST-SQUARES PROBLEMS FOR MATRICES WITH DISPLACEMENT STRUCTURE [J].
CHUN, J ;
KAILATH, T .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1991, 12 (01) :128-145
[7]  
Cline R. E., 1974, Linear Algebra and Its Applications, V8, P25, DOI 10.1016/0024-3795(74)90004-4
[8]  
GERASOULIS A, 1987, MATH COMPUT, V50, P179
[9]   CIRCULANTS, DISPLACEMENTS AND DECOMPOSITIONS OF MATRICES [J].
GOHBERG, I ;
OLSHEVSKY, V .
INTEGRAL EQUATIONS AND OPERATOR THEORY, 1992, 15 (05) :730-743
[10]  
GOHBERG I, UNPUB FAST ALGORITHM
12