×

zbMATH — the first resource for mathematics

An application of the discrete-time Toda lattice to the progressive algorithm by Lanczos and related problems. (English) Zbl 1392.65097
The aim in this article is to point out how the Toda lattice is used in the Lanczos algorithm through the quotient-difference algorithm and its progressive form. The multistep progressive algorithm for solving linear systems is also introduced. The extended Lanczos parameters can be received using the progressive form of quotient-difference algorithm with highly accuracy in a lower computational cost. Results of numerical experiments are also given.
MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
37J35 Completely integrable finite-dimensional Hamiltonian systems, integration methods, integrability tests
65F30 Other matrix algorithms (MSC2010)
15A42 Inequalities involving eigenvalues and eigenvectors
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brezinski, C., A transpose-free Lanczos/Orthodir algorithm for linear systems, C. R. Acad. Sci., Paris I, 324, 349-354, (1997) · Zbl 0877.65013
[2] Brezinski, C.; Redivo-Zaglia, M., Transpose-free Lanczos-type algorithms for nonsymmetric linear systems, Numer. Algorithms, 17, 67-103, (1998) · Zbl 0907.65031
[3] Brezinski, C.; Redivo-Zaglia, M., Variations of Lanczos’ tridiagonalization process, Calcolo, 37, 159-179, (2000) · Zbl 0973.65032
[4] Brezinski, C.; Redivo-Zaglia, M.; Sadok, H., A review of formal orthogonality in Lanczos-based methods, J. Comput. Appl. Math., 140, 81-98, (2002) · Zbl 0996.65031
[5] Brown, J. D.; Chu, M. T.; Ellison, D. C.; Plemmons, R. J., (1994), Philadelphia, PA: SIAM, Philadelphia, PA
[6] Bueno, M. I.; Marcellán, F., Darboux transformation and perturbation of linear functionals, Linear Algebr. Appl., 384, 215-242, (2004) · Zbl 1055.42016
[7] Chihara, T. S., An Introduction to Orthogonal Polynomials, (1978), New York: Gordon & Breach, New York · Zbl 0389.33008
[8] Dette, H.; Studden, W., The Theory of Canonical Moments with Applications in Statistics, Probability and Analysis, (1997), New York: Wiley, New York
[9] Eisenstat, S. C.; Elman, H. C.; Schults, M. H., Variational iteration methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 20, 345-357, (1983) · Zbl 0524.65019
[10] Faddeev, D. K.; Faddeeva, V. N., Computational Methods of Linear Algebra, (1963), Moscow: Fizmatgiz, Moscow · Zbl 0112.07503
[11] Fernando, K. V.; Parlett, B. N., Accurate singular values and differential qd algorithms, Numer. Math., 67, 191-229, (1994) · Zbl 0814.65036
[12] Francis, J., The QR transformation, parts I–II, Computer J., 4, (19611962)
[13] Gautschi, W., Orthogonal polynomials: applications and computation, Acta Numer., 5, 45-119, (1996) · Zbl 0871.65011
[14] Golub, G. H.; O’leary, D. P., Some history of the conjugate gradient and Lanczos algorithms: 1948–1976, SIAM Rev., 31, 50-102, (1989) · Zbl 0673.65017
[15] Golub, G. H.; van Loan, C. F., Matrix Computations, (1996), Baltimore, MD: The Johns Hopkins University Press, Baltimore, MD · Zbl 0865.65009
[16] Golub, G. H.; Welsch, J. H., Calculation of Gauss quadrature rules, Math. Comput., 23, 221-230, (1969) · Zbl 0179.21901
[17] Henrici, P., Applied and Computational Complex Analysis, vol 1, (1974), New York: Wiley, New York
[18] Henrici, P., Applied and Computational Complex Analysis, vol 2, (1977), New York: Wiley, New York · Zbl 0377.30002
[19] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl Bur. Stand., 49, 409-436, (1952) · Zbl 0048.09901
[20] Higham, N. J., The accuracy of floating point summation, SIAM J. Sci. Comput., 14, 783-799, (1993) · Zbl 0788.65053
[21] Hirota, R.; Hirota, R.; Hirota, R., Nonlinear partial difference equations I–V. Nonlinear partial difference equations I–V. Nonlinear partial difference equations I–V, J. Phys. Soc. Japan. J. Phys. Soc. Japan. J. Phys. Soc. Japan, 46, 312-319, (1979)
[22] Hirota, R., Discrete analogue of a generalized Toda equation, J. Phys. Soc. Japan, 50, 37853891, (1981)
[23] Kublanovskaya, V. N., On some algorithms for the solution of the compute eigenvalue problem, USSR Comput. Math. Phys., 3, 637-657, (1961) · Zbl 0128.11702
[24] Lanczos, C., An iteration method for solution of the eigenvalue problem of linear differential and integral operators, J. Res. Natl Bur. Stand., 45, 255-282, (1950)
[25] Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Natl Bur. Stand., 49, 33-53, (1952)
[26] Laurie, D. P., Accurate recovery of recursion coefficients from Gaussian quadrature formulas, J. Comput. Appl. Math., 112, 165-180, (1999) · Zbl 0942.65022
[27] Maurant, G., The Lanczos and Conjugate Gradient Algorithms, (2006), Philadelphia, PA: SIAM, Philadelphia, PA
[28] Moser, J. K., Finitely many mass points on the line under the influence of an exponential potential an integrable system, Dynamical Systems. Theory and Applications, 467-497, (1975), Berlin: Springer, Berlin
[29] Nakamura, Y., The BCH-Goppa decoding as a moment problem and a tau-function over finite fields, Phys. Lett. A, 223, 75-81, (1996) · Zbl 1037.94547
[30] Nakamura, Y., Calculating Laplace transforms in terms of the Toda molecule, SIAM J. Sci. Comput., 20, 306-317, (1999) · Zbl 0932.37060
[31] Papageorgiou, V.; Grammaticos, B.; Ramani, A., Orthogonal polynomial approach to discrete Lax pairs for initial boundary-value problems of the QD algorithm, Lett. Math. Phys., 34, 91-101, (1995) · Zbl 0831.58028
[32] Parlett, B. N.; Marques, O. A., An implementation of the dqds algorithm (positive case), Linear Algebr. Appl., 309, 217-259, (2000) · Zbl 0952.65031
[33] Rutishauser, H., Der quotienten-differenzen-algorithmus, Z. Angew. Math. Phys., 5, 233-251, (1954) · Zbl 0055.34702
[34] Rutishauser, H., Solution of eigenvalue problems with the LR-transformation, Nat. Bur. Stand. Appl. Math. Ser., 49, 47-81, (1958)
[35] Rutishauser, H., On a modification of the QD-algorithm with Graeffe-type convergence, J. Appl. Math. Phys., 13, 493-496, (1962) · Zbl 0113.10702
[36] Rutishauser, H., Lectures on Numerical Mathematics, (1990), Boston, MA: Birkhäuser, Boston, MA
[37] Sogo, K., Toda molecule equation and quotient-difference method, J. Phys. Soc. Japan, 62, 1081-1084, (1993) · Zbl 0972.82558
[38] Stiefel, E., Relaxationsmethoden bester Strategie zur Lösung linearer Gleichungssysteme, Comment. Math. Helv., 29, 157-179, (1955) · Zbl 0066.36703
[39] Symes, W. W., The QR algorithms and scattering for the finite nonperiodic Toda lattice, Physica D, 4, 275-280, (1982) · Zbl 1194.37112
[40] Toda, M., Vibration of a chain with nonlinear interaction, J. Phys. Soc. Japan, 22, 431-436, (1967)
[41] Toda, M., Wave propagation in anharmonic lattices, J. Phys. Soc. Japan, 23, 501-506, (1967)
[42] Toda, M.; Toda, M., Theory of Nonlinear Lattice. Theory of Nonlinear Lattice, (1981), Tokyo: Iwanami Publishing, Tokyo: Tokyo: Iwanami Publishing, Tokyo, Berlin: Springer, Tokyo: Iwanami Publishing, Tokyo: Tokyo: Iwanami Publishing, Tokyo, Berlin
[43] Uvarov, U. B., The connection between system of polynomials orthogonal with respect to different distribution functions, USSR Comput. Math. Math. Phys., 9, 25-360, (1969) · Zbl 0231.42013
[44] Viennot, G., A combinatorial theory for general orthogonal polynomials with extensions and applications, Orthogonal Polynomials and Applications, 139-157, (1985), Berlin: Springer, Berlin
[45] Watkins, D. S., Fundamentals of Matrix Computations, (2002), New York: Wiley, New York · Zbl 1005.65027
[46] Wilkinson, J. H., The Algebraic Eigenvalue Problem, (1965), Oxford: Oxford University Press, Oxford · Zbl 0258.65037
[47] Yamashita, T.; Kimura, K.; Yamamoto, Y., A new subtraction-free formula for lower bounds of the minimal singular value of an upper bidiagonal matrix, Numer. Algorithms, 69, 893-912, (2015) · Zbl 1329.65079
[48] Yound, D. M.; Jea, K. C., Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods, Linear Algebr. Appl., 34, 159-194, (1980) · Zbl 0463.65025
[49] Zhedanov, A., Rational spectral transformations and orthogonal polynomials, J. Comput. Appl. Math., 85, 67-86, (1997) · Zbl 0918.42016
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.