{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:13Z","timestamp":1740133933909,"version":"3.37.3"},"reference-count":35,"publisher":"World Scientific Pub Co Pte Ltd","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:p> Reduction of an [Formula: see text] nonsymmetric matrix to Hessenberg form which takes [Formula: see text] flops and [Formula: see text] I\/Os is a major performance bottleneck in the computing of its eigenvalues. Usually to improve the performance, this Hessenberg reduction is computed in two steps: the first one reduces the matrix to a banded Hessenberg form, and the second one further reduces it to Hessenberg form by incorporating more matrix-matrix operations in the computation. We analyse the two steps of the Hessenberg reduction problem on the external memory model (of Aggarwal and Vitter) for their I\/O complexities. We propose and analyse a tile based algorithm for the first step of the reduction and show that it takes [Formula: see text] I\/Os. For the reduction of a banded Hessenberg matrix of bandwidth [Formula: see text] to Hessenberg form, we propose an algorithm, which uses tight packing of bulges, and requires only [Formula: see text] I\/Os. Combining the results of the two steps of the reduction, we show that the Hessenberg reduction can be performed in [Formula: see text] I\/Os, when [Formula: see text] is sufficiently large. To the best of our knowledge, the proposed algorithm is the first I\/O optimal algorithm for Hessenberg reduction; the worst case I\/O complexity matches the known lower bound of the problem. <\/jats:p>","DOI":"10.1142\/s0129054119500266","type":"journal-article","created":{"date-parts":[[2019,12,13]],"date-time":"2019-12-13T02:01:30Z","timestamp":1576202490000},"page":"1279-1300","source":"Crossref","is-referenced-by-count":0,"title":["An Input\/Output Efficient Algorithm for Hessenberg Reduction"],"prefix":"10.1142","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9203-7174","authenticated-orcid":false,"given":"Sraban Kumar","family":"Mohanty","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, PDPM Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, MP, India"}]},{"given":"G.","family":"Sajith","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, Indian Institute of Technology Guwahati, Assam, India"}]}],"member":"219","published-online":{"date-parts":[[2019,12,12]]},"reference":[{"key":"S0129054119500266BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"S0129054119500266BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/509593.509622"},{"volume-title":"LAPACK Users\u2019 Guide","year":"1995","author":"Anderson E.","key":"S0129054119500266BIB004"},{"key":"S0129054119500266BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1021-x"},{"key":"S0129054119500266BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.10.001"},{"key":"S0129054119500266BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"S0129054119500266BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00015-G"},{"key":"S0129054119500266BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/SHPCC.1994.296622"},{"key":"S0129054119500266BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365735"},{"key":"S0129054119500266BIB012","first-page":"139","volume-title":"Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chiang Y.-J.","year":"1995"},{"key":"S0129054119500266BIB013","doi-asserted-by":"publisher","DOI":"10.1109\/FMPC.1992.234898"},{"key":"S0129054119500266BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF02140776"},{"volume-title":"Lecture Notes from the EEF Summer School on Massive Data Sets","year":"2002","author":"Demaine E. D.","key":"S0129054119500266BIB015"},{"key":"S0129054119500266BIB016","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719611"},{"key":"S0129054119500266BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90367-1"},{"key":"S0129054119500266BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(92)90011-U"},{"key":"S0129054119500266BIB019","first-page":"129","volume-title":"Supercomputing 88. Vol. II: Science and Applications Proceedings","volume":"2","author":"Dubrulle A. A.","year":"1988"},{"key":"S0129054119500266BIB020","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503428693"},{"key":"S0129054119500266BIB021","series-title":"Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins Studies in the Mathematical Sciences","volume-title":"Matrix Computations","author":"Golub G. H.","year":"1996"},{"key":"S0129054119500266BIB022","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366816"},{"key":"S0129054119500266BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00041-1"},{"key":"S0129054119500266BIB024","doi-asserted-by":"publisher","DOI":"10.1137\/0914078"},{"key":"S0129054119500266BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00064-X"},{"key":"S0129054119500266BIB026","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595280211"},{"key":"S0129054119500266BIB029","doi-asserted-by":"publisher","DOI":"10.1007\/BF02161358"},{"volume-title":"19th IEEE Annual International Conference on High Performance Computing (HiPC12)","author":"Mohanty S. K.","key":"S0129054119500266BIB031"},{"key":"S0129054119500266BIB032","doi-asserted-by":"publisher","DOI":"10.1145\/1141885.1141887"},{"issue":"1","key":"S0129054119500266BIB034","first-page":"17","volume":"84","author":"Roh K.","year":"2008","journal-title":"Fund. Inform."},{"key":"S0129054119500266BIB035","doi-asserted-by":"publisher","DOI":"10.1137\/0910005"},{"key":"S0129054119500266BIB037","doi-asserted-by":"publisher","DOI":"10.1145\/236017.236029"},{"volume-title":"Using PLAPACK: Parallel Linear Algebra Package","year":"1997","author":"Van de Geijn R. A.","key":"S0129054119500266BIB038"},{"key":"S0129054119500266BIB039","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"S0129054119500266BIB040","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0005-6_10"},{"key":"S0129054119500266BIB041","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185207"},{"key":"S0129054119500266BIB042","doi-asserted-by":"publisher","DOI":"10.1002\/0471249718"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119500266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,13]],"date-time":"2019-12-13T02:01:43Z","timestamp":1576202503000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119500266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":35,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1142\/S0129054119500266"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119500266","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2019,12]]}}}