{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T00:47:40Z","timestamp":1753922860632,"version":"3.41.2"},"reference-count":37,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2023,8,7]],"date-time":"2023-08-07T00:00:00Z","timestamp":1691366400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation of Sri Lanka","doi-asserted-by":"publisher","award":["DMS\u20101819166","DMS\u20102111007"],"award-info":[{"award-number":["DMS\u20101819166","DMS\u20102111007"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Numerical Linear Algebra App"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this article, we consider the rank\u2010structured approximation of one important type of Cauchy matrix. This approximation plays a key role in some structured matrix methods such as stable and efficient direct solvers and other algorithms for Toeplitz matrices and certain kernel matrices. Previous rank\u2010structured approximations (specifically hierarchically semiseparable, or HSS, approximations) for such a matrix of size  cost at least  complexity. Here, we show how to construct an HSS approximation with sublinear (specifically, ) complexity. The main ideas include extensive computation reuse and an analytical far\u2010field compression strategy. Low\u2010rank compression at each hierarchical level is restricted to just a single off\u2010diagonal block row, and a resulting basis matrix is then reused for other off\u2010diagonal block rows as well as off\u2010diagonal block columns. The relationships among the off\u2010diagonal blocks are rigorously analyzed. The far\u2010field compression uses an analytical proxy point method where we optimize the choice of some parameters so as to obtain accurate low\u2010rank approximations. Both the basis reuse ideas and the resulting analytical hierarchical compression scheme can be generalized to some other kernel matrices and are useful for accelerating relevant rank\u2010structured approximations (though not subsequent operations like matrix\u2010vector multiplications).<\/jats:p>","DOI":"10.1002\/nla.2526","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T05:55:15Z","timestamp":1691474115000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Rank\u2010structured approximation of some Cauchy matrices with sublinear complexity"],"prefix":"10.1002","volume":"31","author":[{"given":"Mikhail","family":"Lepilov","sequence":"first","affiliation":[{"name":"Department of Mathematics Purdue University  West Lafayette Indiana USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianlin","family":"Xia","sequence":"additional","affiliation":[{"name":"Department of Mathematics Purdue University  West Lafayette Indiana USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2023,8,7]]},"reference":[{"key":"e_1_2_12_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1995-1312096-X"},{"key":"e_1_2_12_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4228-4_5"},{"key":"e_1_2_12_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(79)90124-0"},{"key":"e_1_2_12_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-1023051-7"},{"key":"e_1_2_12_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/040617200"},{"key":"e_1_2_12_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2005.03.011"},{"key":"e_1_2_12_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2014.09.004"},{"key":"e_1_2_12_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/120895755"},{"key":"e_1_2_12_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/110831982"},{"key":"e_1_2_12_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436652"},{"key":"e_1_2_12_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.691"},{"key":"e_1_2_12_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1438633"},{"key":"e_1_2_12_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1018812"},{"key":"e_1_2_12_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914966"},{"key":"e_1_2_12_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/140986815"},{"key":"e_1_2_12_17_1","unstructured":"XiaJ LepilovM.Why are many circulant matrices rank structured?Preprint."},{"key":"e_1_2_12_18_1","unstructured":"LepilovM XiaJ.The proxy point method for analytic kernels with applications to some Toeplitz matrices. Preprint."},{"key":"e_1_2_12_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2005.1582739"},{"key":"e_1_2_12_20_1","first-page":"S24","article-title":"Data\u2010driven construction of hierarchical matrices with nested bases","author":"Cai D","year":"2022","journal-title":"SIAM J Sci Comput"},{"key":"e_1_2_12_21_1","first-page":"749","volume-title":"34th IEEE international parallel and distributed processing symposium (IPDPS)","author":"Erlandson L","year":"2020"},{"key":"e_1_2_12_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2204"},{"key":"e_1_2_12_23_1","doi-asserted-by":"publisher","DOI":"10.1553\/etna_vol54s581"},{"key":"e_1_2_12_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"e_1_2_12_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2004.10.033"},{"key":"e_1_2_12_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2005.09.010"},{"key":"e_1_2_12_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2003.11.021"},{"key":"e_1_2_12_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-012-9679-2"},{"key":"e_1_2_12_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1247838"},{"key":"e_1_2_12_30_1","first-page":"89","article-title":"A sparse matrix arithmetic based on H$$ H $$\u2010matrices. Part I: introduction to H$$ H $$\u2010matrices","volume":"62","author":"Hackbusch W","year":"1999","journal-title":"Comput Secur"},{"key":"e_1_2_12_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/110827788"},{"key":"e_1_2_12_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"e_1_2_12_33_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"e_1_2_12_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.04.002"},{"key":"e_1_2_12_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21577"},{"key":"e_1_2_12_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575706"},{"key":"e_1_2_12_37_1","doi-asserted-by":"publisher","DOI":"10.4208\/csiam-am.2021.nla.02"},{"key":"e_1_2_12_38_1","first-page":"207","article-title":"Hierarchical matrices based on a weak admissibility criterion","volume":"73","author":"Hackbusch W","year":"2004","journal-title":"Comput Secur"}],"container-title":["Numerical Linear Algebra with Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T07:23:47Z","timestamp":1702970627000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/nla.2526"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["10.1002\/nla.2526"],"URL":"https:\/\/doi.org\/10.1002\/nla.2526","archive":["Portico"],"relation":{},"ISSN":["1070-5325","1099-1506"],"issn-type":[{"type":"print","value":"1070-5325"},{"type":"electronic","value":"1099-1506"}],"subject":[],"published":{"date-parts":[[2023,8,7]]},"assertion":[{"value":"2022-08-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e2526"}}