{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T04:46:25Z","timestamp":1766983585434,"version":"3.30.1"},"reference-count":35,"publisher":"American Mathematical Society (AMS)","issue":"218","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

In this paper we are concerned with the solution ofn<\/mml:mi>\u00d7<\/mml:mo>n<\/mml:mi><\/mml:mrow>n\\times n<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>Hermitian Toeplitz systems with nonnegative generating functionsf<\/mml:mi>f<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. The preconditioned conjugate gradient (PCG) method with the well\u2013known circulant preconditioners fails in the case wheref<\/mml:mi>f<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>has zeros. In this paper we consider as preconditioners band\u2013Toeplitz matrices generated by trigonometric polynomialsg<\/mml:mi>g<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>of fixed degreel<\/mml:mi>l<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. We use different strategies of approximation off<\/mml:mi>f<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>to devise a polynomialg<\/mml:mi>g<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>which has some analytical properties off<\/mml:mi>f<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>, is easily computable and is such that the corresponding preconditioned system has a condition number bounded by a constant independent ofn<\/mml:mi>n<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>. For each strategy we analyze the cost per iteration and the number of iterations required for the convergence within a preassigned accuracy. We obtain different estimates ofl<\/mml:mi>l<\/mml:annotation><\/mml:semantics><\/mml:math><\/inline-formula>for which the total cost of the proposed PCG methods is optimal and the related rates of convergence are superlinear. Finally, for the most economical strategy, we perform various numerical experiments which fully confirm the effectiveness of approximation theory tools in the solution of this kind of linear algebra problems.<\/p>","DOI":"10.1090\/s0025-5718-97-00833-8","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T22:14:44Z","timestamp":1027721684000},"page":"651-665","source":"Crossref","is-referenced-by-count":54,"title":["Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems"],"prefix":"10.1090","volume":"66","author":[{"given":"Stefano","family":"Serra","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1997]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1109\/t-c.1974.223784","article-title":"Discrete cosine transform","volume":"C-23","author":"Ahmed, N.","year":"1974","journal-title":"IEEE Trans. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9340","issn-type":"print"},{"key":"2","series-title":"Computer Science and Applied Mathematics","isbn-type":"print","volume-title":"Finite element solution of boundary value problems","author":"Axelsson, O.","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/0120687801"},{"issue":"5","key":"3","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/BF01389447","article-title":"On the eigenvalue distribution of a class of preconditioning methods","volume":"48","author":"Axelsson, Owe","year":"1986","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"1-2","key":"4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF02575746","article-title":"Matrix structures in parallel matrix computations","volume":"25","author":"Bini, D.","year":"1988","journal-title":"Calcolo","ISSN":"https:\/\/id.crossref.org\/issn\/0008-0624","issn-type":"print"},{"key":"5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0024-3795(83)80009-3","article-title":"Spectral and computational properties of band symmetric Toeplitz matrices","volume":"52\/53","author":"Bini, Dario","year":"1983","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0614035","article-title":"On a matrix algebra related to the discrete Hartley transform","volume":"14","author":"Bini, Dario","year":"1993","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"3","key":"7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1093\/imanum\/11.3.333","article-title":"Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions","volume":"11","author":"Chan, Raymond H.","year":"1991","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"key":"8","doi-asserted-by":"crossref","unstructured":"R.H. Chan, W. Ching, \u201cToeplitz\u2013circulant preconditioners for Toeplitz systems and their applications to queueing network with batch arrivals\u201d, SIAM J. Sci. Comp., 17 (1996), 762\u2013772.","DOI":"10.1137\/S1064827594266581"},{"key":"9","unstructured":"R.H. Chan, Q. Chang, H. Sun, \u201cMultigrid method for ill-conditioned symmetric Toeplitz systems\u201d, personal communication."},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0910009","article-title":"Toeplitz equations by conjugate gradients with circulant preconditioner","volume":"10","author":"Chan, Raymond H.","year":"1989","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/0915011","article-title":"Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems","volume":"15","author":"Chan, Raymond H.","year":"1994","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"12","doi-asserted-by":"crossref","unstructured":"R.H. Chan, P. Tang, \u201cConstrained minimax approximation and optimal preconditioners for Toeplitz matrices\u201d, Numer. Alg., 5 (1993), 353\u2013364.","DOI":"10.1007\/BF02109196"},{"issue":"4","key":"13","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/0909051","article-title":"An optimal circulant preconditioner for Toeplitz systems","volume":"9","author":"Chan, Tony F.","year":"1988","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"},{"key":"14","series-title":"A Wiley-Interscience Publication","isbn-type":"print","volume-title":"Circulant matrices","author":"Davis, Philip J.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0471057711"},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/0916041","article-title":"Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices","volume":"16","author":"Di Benedetto, Fabio","year":"1995","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"6","key":"16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0898-1221(93)90297-9","article-title":"CG preconditioning for Toeplitz matrices","volume":"25","author":"Di Benedetto, Fabio","year":"1993","journal-title":"Comput. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"print"},{"issue":"3-4","key":"17","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/BF02575816","article-title":"Multigrid methods for Toeplitz matrices","volume":"28","author":"Fiorentino, G.","year":"1991","journal-title":"Calcolo","ISSN":"https:\/\/id.crossref.org\/issn\/0008-0624","issn-type":"print"},{"key":"18","series-title":"Translations of Mathematical Monographs, Vol. 41","volume-title":"Convolution equations and projection methods for their solution","author":"Gohberg, I. C.","year":"1974"},{"key":"19","series-title":"Johns Hopkins Series in the Mathematical Sciences","isbn-type":"print","volume-title":"Matrix computations","volume":"3","author":"Golub, Gene H.","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0801830109"},{"key":"20","isbn-type":"print","volume-title":"Toeplitz forms and their applications","author":"Grenander, Ulf","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/082840321X","edition":"2"},{"key":"21","isbn-type":"print","volume-title":"Hankel and Toeplitz matrices and forms","author":"Iohvidov, I. S.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/3764330902"},{"key":"22","unstructured":"D. Jackson, The Theory of Approximation. American Mathematical Society, New York, 1930."},{"key":"23","series-title":"Springer Tracts in Natural Philosophy, Vol. 13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-85643-3","volume-title":"Approximation of functions: Theory and numerical methods","author":"Meinardus, G\u00fcnter","year":"1967"},{"key":"24","unstructured":"A. Oppenheim, Applications of Digital Signal Processing. Prentice\u2013Hall, Englewood Cliffs, 1978."},{"key":"25","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1093\/comjnl\/9.4.404","article-title":"On the maximum errors of polynomial approximations defined by interpolation and by least squares criteria","volume":"9","author":"Powell, M. J. D.","year":"1967","journal-title":"Comput. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4620","issn-type":"print"},{"key":"26","unstructured":"E.J. Remes, \u201cSur le calcul effectif des polynomes d\u2019approximation de Tchebichef\u201d Compt. Rend. Acad. Sci. Paris, 199 (1934), 337\u2013340."},{"key":"27","doi-asserted-by":"crossref","unstructured":"S. Serra, \u201cPreconditioning strategies for asymptotically ill\u2013conditioned block Toeplitz systems\u201d, BIT, 34 (1994), pp. 579\u2013594.","DOI":"10.1007\/BF01934269"},{"key":"28","doi-asserted-by":"crossref","unstructured":"S. Serra, \u201cConditioning and solution of Hermitian (block) Toeplitz systems by means of preconditioned conjugate gradient methods\u201d, Proc. in Advanced Signal Processing Algorithms, Architectures, and Implementations - SPIE conference, F. Luk Ed., San Diego (CA), july 1995, pp. 326\u2013337.","DOI":"10.1117\/12.211409"},{"key":"29","doi-asserted-by":"crossref","unstructured":"S. Serra, \u201cPreconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions\u201d, SIAM J. Matr. Anal. Appl., 17 (1996), pp. 1007\u20131019.","DOI":"10.1137\/S089547989427141X"},{"key":"30","unstructured":"S. Serra, \u201cOn the extreme eigenvalues of Hermitian (block) Toeplitz matrices\u201d, Linear Algebra Appl., to appear."},{"key":"31","doi-asserted-by":"crossref","unstructured":"S. Serra, \u201cOn the extreme spectral properties of Toeplitz matrices generated by \ud835\udc3f\u00b9 functions with several minima (maxima)\u201d, BIT, 36 (1996), 135\u2013142.","DOI":"10.1007\/BF01740550"},{"key":"32","unstructured":"S. Serra, \u201cAsymptotic results on the spectra of preconditioned Toeplitz matrices and some applications\u201d, TR nr. 9 University of Calabria, (1995)."},{"issue":"184","key":"33","doi-asserted-by":"publisher","first-page":"721","DOI":"10.2307\/2008772","article-title":"A fast algorithm for linear complex Chebyshev approximations","volume":"51","author":"Tang, Ping Tak Peter","year":"1988","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"34","series-title":"Frontiers in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970999","volume-title":"Computational frameworks for the fast Fourier transform","volume":"10","author":"Van Loan, Charles","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712858"},{"issue":"4","key":"35","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1137\/0912044","article-title":"Parallel algorithms for banded linear systems","volume":"12","author":"Wright, Stephen J.","year":"1991","journal-title":"SIAM J. Sci. Statist. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-5204","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1997-66-218\/S0025-5718-97-00833-8\/S0025-5718-97-00833-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1997-66-218\/S0025-5718-97-00833-8\/S0025-5718-97-00833-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,8]],"date-time":"2024-12-08T10:41:04Z","timestamp":1733654464000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1997-66-218\/S0025-5718-97-00833-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"references-count":35,"journal-issue":{"issue":"218","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["S0025-5718-97-00833-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-97-00833-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"type":"print","value":"0025-5718"},{"type":"electronic","value":"1088-6842"}],"subject":[],"published":{"date-parts":[[1997]]}}}