{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:48:16Z","timestamp":1776721696498,"version":"3.51.2"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"213","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n The eigenvalue clustering of matrices\n \n \n \n \n \n S<\/mml:mi>\n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msubsup>\n \n A<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n S_n^{-1}A_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n \n \n C<\/mml:mi>\n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msubsup>\n \n A<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n C_n^{-1}A_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is experimentally studied, where\n \n \n \n \n A<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n A_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ,\n \n \n \n \n S<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n S_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n \n C<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n C_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n respectively are Toeplitz matrices, Strang, and optimal circulant preconditioners generated by the Fourier expansion of a function\n \n \n \n \n f<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n f(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Some illustrations are given to show how the clustering depends on the smoothness of\n \n \n \n \n f<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n f(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and which preconditioner is preferable. An original technique for experimental exploration of the clustering rate is presented. This technique is based on the bisection idea and on the Toeplitz decomposition of a three-matrix product\n \n \n \n \n C<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n <\/mml:mrow>\n CAC<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n A<\/mml:mi>\n A<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a Toeplitz matrix and\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a circulant. In particular, it is proved that the Toeplitz (displacement) rank of\n \n \n \n \n C<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n <\/mml:mrow>\n CAC<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is not greater than 4, provided that\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n A<\/mml:mi>\n A<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are symmetric.\n <\/p>","DOI":"10.1090\/s0025-5718-96-00682-5","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"137-150","source":"Crossref","is-referenced-by-count":35,"title":["Which circulant preconditioner is better?"],"prefix":"10.1090","volume":"65","author":[{"given":"V.","family":"Strela","sequence":"first","affiliation":[]},{"given":"E.","family":"Tyrtyshnikov","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1996]]},"reference":[{"issue":"5","key":"1","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":"2","key":"2","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/0726029","article-title":"The spectrum of a family of circulant preconditioned Toeplitz systems","volume":"26","author":"Chan, Raymond H.","year":"1989","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"3","key":"3","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1137\/0728046","article-title":"The spectra of super-optimal circulant preconditioned Toeplitz systems","volume":"28","author":"Chan, Raymond H.","year":"1991","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"1","key":"4","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":"4","key":"5","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":"6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0024-3795(86)90279-X","article-title":"Efficient solution of linear systems of equations with recursive structure","volume":"80","author":"Gohberg, I.","year":"1986","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0022-247X(79)90124-0","article-title":"Displacement ranks of matrices and linear equations","volume":"68","author":"Kailath, Thomas","year":"1979","journal-title":"J. Math. Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-247X","issn-type":"print"},{"key":"8","doi-asserted-by":"crossref","unstructured":"G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986), 171\u2013176.","DOI":"10.1002\/sapm1986742171"},{"key":"9","unstructured":"V. Strela, Exploration of circulant preconditioning properties, Matrix Methods and Algorithms, IVM RAN, Moscow, 1993, pp. 9\u201346."},{"key":"10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0024-3795(91)90375-7","article-title":"A decomposition of Toeplitz matrices and optimal circulant preconditioning","volume":"154\/156","author":"Tismenetsky, Miron","year":"1991","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"11","unstructured":"E. Tyrtyshnikov, Toeplitz matrices, some of their analogues and applications, Dept. Numer. Math., USSR Acad. of Sci., Moscow (1989) (in Russian)."},{"issue":"2","key":"12","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1137\/0613030","article-title":"Optimal and superoptimal circulant preconditioners","volume":"13","author":"Tyrtyshnikov, Evgenij E.","year":"1992","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"13","unstructured":"\\bysame, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. (to appear)."},{"key":"14","doi-asserted-by":"crossref","unstructured":"\\bysame, Circulant preconditioners with unbounded inverses, Linear Algebra Appl. 216 (1995), 1\u201323.","DOI":"10.1016\/0024-3795(93)00092-E"},{"key":"15","unstructured":"\\bysame, Fast and parallel inertia finder for Toeplitz expanded matrices, to appear."},{"issue":"204","key":"16","doi-asserted-by":"publisher","first-page":"701","DOI":"10.2307\/2153248","article-title":"Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions","volume":"61","author":"Yeung, Man-Chung","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00682-5\/S0025-5718-96-00682-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00682-5\/S0025-5718-96-00682-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:01:46Z","timestamp":1776718906000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-213\/S0025-5718-96-00682-5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":16,"journal-issue":{"issue":"213","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["S0025-5718-96-00682-5"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-96-00682-5","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1996]]}}}