×

Hartley-type algebras in displacement and optimization strategies. (English) Zbl 1044.65050

The purpose of this paper is to show that a class of structural algebras, the Hartley-type (Ht) algebras linked in different ways to the Hartley transform, are extremly useful in solving both linear and nonlinear (minimizaton) problems. The matrix representations obtained in this paper are classical displacement formulas and lead to efficient Toeplitz inversion formulas (the inverse is rewritten in terms of a number of simple matrices which can be fastly multiplied by vectors) competitive with the well known Ammar-Gader formula based on circulant algebras.
The best least squares approximation is exploited as a preconditioner in quasi-Newton methods (QN) for unconstrained minimization. For novel \(L\)QN minimization methods an algebra \(L\) (\(L=\text{Ht})\) of matrices simultnenously diagonalized by a fast unitary transform is used in the iterative scheme of generalized BFGS-type algorithm. The complexity per step of \(L\)QN is \(O(n\log n)\) and only \(O(n)\) memory allocationsare required. It is shown that \(L\)QN methods are linearly convergent.

MSC:

65K05 Numerical mathematical programming methods
90C05 Linear programming
90C30 Nonlinear programming
90C53 Methods of quasi-Newton type
65F35 Numerical computation of matrix norms, conditioning, scaling
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ammar, G.; Gader, P. D., New decompositions of the inverse of a Toeplitz matrix, (Kaashoek, M. A.; van Schuppen, J. H.; Ran, A. C.N., Signal Processing, Scattering and Operator Theory, and Numerical Methods, Proceedings of the International Symposium MTNS-89, vol. III (1990), Birkhäuser: Birkhäuser Boston), 421-428
[2] Ammar, G.; Gader, P. D., A variant of the Gohberg-Semencul formula involving circulant matrices, SIAM J. Matrix Anal. Appl., 12, 534-540 (1991) · Zbl 0739.65015
[3] Ammar, G.; Gragg, W., Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl., 9, 61-76 (1988) · Zbl 0658.65022
[4] Axelsson, O.; Barker, V. A., Finite Element Solution of Boundary Value Problems-Theory and Computation (1984), Academic Press: Academic Press Orlando, FL · Zbl 0537.65072
[5] Axelsson, O.; Lindskög, G., The rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 48, 499-523 (1986) · Zbl 0564.65017
[6] Bevilacqua, R.; Di Fiore, C.; Zellini, P., \(h\)-Space structure in matrix displacement formulas, Calcolo, 33, 11-35 (1996) · Zbl 0906.15008
[7] Bini, D.; Favati, P., On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl., 14, 500-507 (1993) · Zbl 0773.65029
[8] Bini, D.; Pan, V., Improved parallel computations with Toeplitz-like and Hankel-like matrices, Linear Algebra Appl., 188/189, 3-29 (1993) · Zbl 0776.65022
[11] Bozzo, E.; Di Fiore, C., On the use of certain matrix algebras associated with discrete trigonometric transforms in matrix displacement decomposition, SIAM J. Matrix Anal. Appl., 16, 312-326 (1995) · Zbl 0819.65017
[12] Bracewell, R. N., The fast Hartley transform, Proc. IEEE, 72, 1010-1018 (1984)
[13] Chan, R.; Jin, X.; Yeung, M., The circulant operator in the Banach algebra of matrices, Linear Algebra Appl., 149, 41-53 (1991) · Zbl 0717.15017
[14] Chan, R.; Ng, M., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013
[15] Chan, T. F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., 9, 766-771 (1988) · Zbl 0646.65042
[16] Dennis, J. E.; Moré, J. J., Quasi-Newton methods, motivation and theory, SIAM Rev., 19, 46-89 (1977) · Zbl 0356.65041
[17] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Non-linear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[19] Di Fiore, C., Matrix algebras and displacement decompositions, SIAM J. Matrix Anal. Appl., 21, 646-667 (2000) · Zbl 0947.65049
[22] Di Fiore, C.; Zellini, P., Matrix decompositions using displacement rank and classes of commutative matrix algebras, Linear Algebra Appl., 229, 49-99 (1995) · Zbl 0839.15010
[23] Di Fiore, C.; Zellini, P., Matrix displacement decompositions and applications to Toeplitz linear systems, Linear Algebra Appl., 268, 197-225 (1998) · Zbl 0886.65028
[24] Di Fiore, C.; Zellini, P., Matrix algebras in optimal preconditioning, Linear Algebra Appl., 335, 1-54 (2001) · Zbl 0983.65061
[25] Gohberg, I.; Olshevsky, V., Circulants, displacements and decompositions of matrices, Integral Eq. Operator Theor., 15, 730-743 (1992) · Zbl 0772.15010
[26] Gohberg, I.; Semencul, A., On the inversion of finite Toeplitz matrices and their continual analogues (in Russian), Mat. Issled., 7, 2, 201-233 (1972)
[27] Heinig, G., Chebyshev-Hankel matrices and the splitting approach for centrosymmetric Toeplitz-plus-Hankel matrices, Linear Algebra Appl., 327, 181-196 (2001) · Zbl 1012.65026
[28] Heinig, G.; Rost, K., On the inverses of Toeplitz-plus-Hankel matrices, Linear Algebra Appl., 106, 39-52 (1988) · Zbl 0646.15015
[29] Heinig, G.; Rost, K., Hartley transform representations of inverses of real Toeplitz-plus-Hankel matrices, Numer. Funct. Anal. Optim., 21, 175-189 (2000) · Zbl 0958.15006
[30] Heinig, G.; Rost, K., Hartley transform representations of symmetric Toeplitz matrix inverses with application to fast matrix-vector multiplication, SIAM J. Matrix Anal. Appl., 22, 86-105 (2000) · Zbl 0971.47020
[31] Huckle, T., Circulant/skewcirculant matrices as preconditioners for Hermitian Toeplitz systems, (Beauwens, R.; de Groen, P., Iterative Methods in Linear Algebra (1992), Elsevier: Elsevier North-Holland), (IMACS) · Zbl 0785.65031
[32] Jin, X. Q., Hartley preconditioners for Toeplitz systems generated by positive continuous functions, BIT, 34, 367-371 (1994) · Zbl 0813.65069
[33] Kailath, T.; Kung, S.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68, 395-407 (1979) · Zbl 0433.15001
[34] Kailath, T.; Olshevsky, V., Displacement structure approach to discrete trigonometric transform based preconditioners of G. Strung type and of T. Chan type, Calcolo, 33, 191-208 (1996) · Zbl 0907.65034
[35] Kailath, T.; Sayed, A. H., Displacement structure: theory and applications, SIAM Rev., 37, 297-386 (1995) · Zbl 0839.65028
[37] Nocedal, J.; Wright, S. J., Numerical Optimization (1999), Springer: Springer New York · Zbl 0930.65067
[38] Powell, M. J.D., On the convergence of the variable metric algorithm, J. Inst. Math. Appl., 7, 21-36 (1971) · Zbl 0217.52804
[39] Powell, M. J.D., Some global convergence properties of a variable metric algorithm for minimization without exact line searches, (Cottle, R. W.; Lemke, C. E., Nonlinear Programming, SIAM-AMS Proceedings, New York, March 1975, vol. 9 (1976), SIAM: SIAM Providence), 53-72 · Zbl 0338.65038
[40] Serra Capizzano, S., Toeplitz preconditioners constructed from linear approximation processes, SIAM J. Matrix Anal. Appl., 20, 2, 446-465 (1998) · Zbl 0919.65031
[41] Trench, W., A note on a Toeplitz inversion formula, Linear Algebra Appl., 129, 55-61 (1990) · Zbl 0711.15030
[42] Tyrtyshnikov, E. E., Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl., 13, 459-473 (1992) · Zbl 0774.65024
[43] Uniyal, P. R., Transforming real-valued sequences: fast Fourier versus fast Hartley transform algorithms, IEEE Trans. Signal Process., 42, 11, 3249-3254 (1994)
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.