检索结果-内蒙古大学图书馆

An input/output efficient Algorithm for Hessenberg Reduction

iNTERNATioNAL JoURNAL oF FoUNDATioNS oF CoMPUTER SCiENCE 2019年第8期30卷 1279-1300页

作者： Mohanty, Sraban Kumar Sajith, G. PDPM Indian Inst Informat Technol Design & Mfg Comp Sci & Engn Jabalpur MP India Indian Inst Technol Guwahati Comp Sci & Engn Gauhati Assam India

Reduction of an N x N nonsymmetric matrix to Hessenberg form which takes o(N-3) flops and o(N-3/B) 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 o(N-3/B min{t, root M}) i/os. For the reduction of a banded Hessenberg matrix of bandwidth t to Hessenberg form, we propose an algorithm, which uses tight packing of bulges, and requires only o(t(2)N(2)/B + N-3/tB) i/os. Combining the results of the two steps of the reduction, we show that the Hessenberg reduction can be performed in o(N-3/root MB) i/os, when N 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.

关键词： External memory algorithms out-of-core algorithms matrix computations Hessenberg reduction i/o efficient matrix computation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：