文献

J-GLOBAL ID：201802264889730406   整理番号：18A0390658

Strassen様行列乗算の計算の複雑さについて【Powered by NICT】

On the arithmetic complexity of Strassen-like matrix multiplications

著者 (2件)： Cenk Murat (Institute of Applied Mathematics, Middle East Technical University, 06800, Ankara, Turkey) ,  Hasan M. Anwar (Department of Electrical and Computer Engineering, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 3G1, Canada)
資料名： Journal of Symbolic Computation  (Journal of Symbolic Computation)
巻： 80  号： P2  ページ： 484-501  発行年： 2017年 
JST資料番号： D0359D  ISSN： 0747-7171  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 2×2行列を乗算のためのStrassenアルゴリズムは七乗算と18添加を必要とする。次元nの行列のためのこのアルゴリズムの再帰的使用は2Kで(7 n 2.81 6 n 2)の全演算複雑性が得られた。Winogradはこの種行列乗算のための七回の乗算を用いてが最適であることを示した。,2×2行列を七乗算のアルゴリズムはStrassenのようなアルゴリズムと呼ばれる。Winogradも15添加と相加的に最適Strassenのようなアルゴリズムを発見した。このアルゴリズムは8~2K,Strassenのような乗算のための最も良く知られた限界である2Kおよび(3.73 n 2.81 5 n 2)のWinogradの変異体,その演算量は(6 n 2.81 5 n 2)と呼ばれる。本論文では,2KのWinogradの変異体の複雑さを減少させる(5 n 2.81 +0.5 n 2.59 +2 n 2.32 6.5 n 2)にする方法を提案した。全演算複雑性は8~2K,著者らの知る限り,Strassenのような行列乗算アルゴリズムのための最も良く知られた限界を改善するための(3.55 n 2.81 +0.148 n 2.59 +1.02 n 2.32 6.5 n 2)に改善できることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 演算 ,  *計算量 ,  *乗算 ,  アルゴリズム
準シソーラス用語： 複雑性 ,  *行列積 , 【Automatic Indexing@JST】

著者キーワード (5件)： 高速行列乗算 ,  Strassen様行列乗算 ,  計算の複雑さ ,  暗号計算 ,  計算機代数

分類 (1件)： 数値計算  (JE02000J)

タイトルに関連する用語 (2件)： 行列乗算 ,  計算の複雑さ