基本信息来源于合作网站,原文需代理用户跳转至来源网站获取       
摘要:
The first error theory and bounds for Fast Matrix Multiplication based on the Strassen-Winograd algorithms (FastMMW) were formulated in the 70s. The theory introduces the concept, which is now known as weakly-stable error analysis, where the error bounds must use matrix norms instead of component-wise bounds. While the theory debunked the instability myth by using matrix scaling and a clean and simple analysis, its bounds are available only as properties of the whole matrices, which are too coarse, pessimistic, at times used to suggest instability, and are not used for algorithm optimization. We build on top of the original theory in order to reformulate the bounds: we show that tighter norm-wise and component-wise bounds are achievable by orthogonal algorithm optimizations. To achieve even better discrimination and circumvent the use of norm bounds, we develop an error theory by using communication and statistics concepts: we investigate lower and upper bounds, we estimate the practical bounds, and we investigate the algorithmic nature of the error for the class of random matrices. The theory and tools are not limited to random matrices and we can foresee further investigations to different matrix classes and algorithms. We propose new and more accurate algorithms. We show that we can improve theoretically and empirically the maximum absolute error of any FastMMW algorithm by 10% - 20% per recursion (we reduce the error by half for 4 recursions). Our theory and practice, in turn, will provide a kick start for the development of hybrid algorithms as accurate as the vendor GEMM implementation, and in certain cases even more accurate for random matrices.
推荐文章
基于OpenMP的Winograd并行矩阵乘算法应用研究
分子动力学
矩阵乘
Winograd
并行计算
加速比
OpenMP
Better 117C有机硅浸渍树脂在高速牵引电机上的应用研究
有机硅浸渍树脂
牵引电机
线棒
模卡
整机
电性能
改良Winograd术治疗拇趾嵌甲症
Winograd术
拇趾
嵌甲症
内容分析
关键词云
关键词热度
相关文献总数  
(/次)
(/年)
文献信息
篇名 The Better Accuracy of Strassen-Winograd Algorithms (FastMMW)
来源期刊 线性代数与矩阵理论研究进展(英文) 学科 数学
关键词 MATRIX Multiplications ALGORITHMS Performance ERROR Analysis
年,卷(期) 2014,(1) 所属期刊栏目
研究方向 页码范围 9-39
页数 31页 分类号 O1
字数 语种
DOI
五维指标
传播情况
(/次)
(/年)
引文网络
引文网络
二级参考文献  (0)
共引文献  (0)
参考文献  (0)
节点文献
引证文献  (0)
同被引文献  (0)
二级引证文献  (0)
2014(0)
  • 参考文献(0)
  • 二级参考文献(0)
  • 引证文献(0)
  • 二级引证文献(0)
研究主题发展历程
节点文献
MATRIX
Multiplications
ALGORITHMS
Performance
ERROR
Analysis
研究起点
研究来源
研究分支
研究去脉
引文网络交叉学科
相关学者/机构
期刊影响力
线性代数与矩阵理论研究进展(英文)
季刊
2165-333X
武汉市江夏区汤逊湖北路38号光谷总部空间
出版文献量(篇)
93
总下载数(次)
0
论文1v1指导