Complexity of multiplication with vectors for structured matrices. (English) Zbl 0803.65053
A fast algorithm for computing the products of matrices by vectors for some special structured matrices using factor circulants is derived. Numerical results are not given.
Reviewer: S.Filippi (Gießen)
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 65Y20 | Complexity and performance of numerical algorithms |
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1976), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0286.68029 |
| [2] | Ammar, G.; Gader, P., New decompositions of the inverse of a Toeplitz matrix, (Kaashoek, M. A.; van Schuppen, J. H.; Ran, A. C.M., Signal Processing, Scattering and Operator Theory, and Numerical Methods. Signal Processing, Scattering and Operator Theory, and Numerical Methods, Proc. Int. Symp. MTNS-89, Vol. III (1990), Birkhäuser: Birkhäuser Boston), 421-428 · Zbl 0719.65020 |
| [3] | Brent, R.; Gustavson, F.; Yun, D., Fast solutions of Toeplitz systems of equations and computation of Pade approximants, J. Algorithms, 1, 259-295 (1980) · Zbl 0475.65018 |
| [4] | Cabay, S.; Choi, D., Algebraic computations of scaled Padé fractions, SIAM J. Comput., 15, 1, 243-270 (1986) · Zbl 0633.30008 |
| [5] | Canny, J. F.; Kaltofen, E.; Yagati, L., Solving systems of non-linear equations faster, (Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic Algebraic Computing (1989), ACM: ACM New York), 34-42 |
| [6] | Chun, J.; Kailath, T., Divide-and-conquer solutions of least-squares problems for matrices with displacement structure, SIAM J. Matrix Anal. Appl., 12, 1, 128-145 (1991) · Zbl 0718.65031 |
| [7] | Cline, R. E.; Plemmons, R. J.; Worm, G., Generalized inverses of certain Toeplitz matrices, Linear Algebra Appl., 8, 25-33 (1974) · Zbl 0273.15004 |
| [8] | Gerasoulis, A., A fast algorithm for the multiplication of generalized Hilbert matrices with vectors, Math. Comp., 50, 181, 179-188 (1987) · Zbl 0648.65040 |
| [9] | Gohberg, I.; Feldman, I., Convolution Equations and Projection Methods for Their Solutions, (Transl. Math. Monogr., 41 (1974), Amer. Math. Soc) · Zbl 0951.47021 |
| [10] | Gohberg, I.; Olshevsky, V., Circulants, displacements and decompositions of matrices, Integral Equations Operator Theory, 15, 5, 730-743 (1992) · Zbl 0772.15010 |
| [12] | Gohberg, I.; Semencul, A., On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issled., 7, 2, 201-233 (1972), (in Russian) · Zbl 0288.15004 |
| [13] | Heinig, G.; Rost, K., Algebraic Methods for Toeplitz-like Matrices and Operators, (Oper. Theory, 13 (1984), Birkhäuser: Birkhäuser Basel) · Zbl 1084.65030 |
| [14] | Kailath, T.; Kung, S.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68, 395-407 (1979) · Zbl 0433.15001 |
| [15] | Labahn, G.; Choi, D.; Cabay, S., The inverses of block Hankel and block Toeplitz matrices, SIAM J. Comput., 19, 1, 98-123 (1990) · Zbl 0716.15003 |
| [16] | Lancaster, P.; Tismenetzky, M., Theory of Matrices with Applications (1985), Academic: Academic Orlando, Fla · Zbl 0558.15001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
