Methods for Mitigating and Eliminating Error in Hybrid Matrix Multiply Algorithms.

摘要

High performance dense matrix multiply implementations have largely reached their limit in terms of performance as efficiencies are very near 100%. In order to further increase performance, matrix multiply algorithms that are asymptotically faster than O(n3) must be used to reduce the overall amount of computation required. Asymptotically fast matrix multiply algorithms however have adverse affects on accuracy, and until recently, this accuracy problem was believed to be uncorrectable. Because of this, the adoption of hybrid dense matrix multiply algorithms (algorithms that combine asymptotically fast matrix multiply algorithms with high performance matrix multiply implementations), particularly by linear algebra library authors, has been non-existent. In this dissertation we present several solutions that in addition to mitigating or eliminating the error added by the asymptotically fast matrix multiply algorithm, (demonstrating that it is possible to use hybrid matrix multiply algorithms without adversely affecting accuracy), can also be used by themselves to improve the accuracy of standard matrix multiply implementations, when additional accuracy is required.