کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4945968 | 1364075 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the arithmetic complexity of Strassen-like matrix multiplications
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The Strassen algorithm for multiplying 2Ã2 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n2.81â6n2) for n=2k. Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2Ã2 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Strassen-like algorithm with 15 additions. This algorithm is called the Winograd's variant, whose arithmetic complexity is (6n2.81â5n2) for n=2k and (3.73n2.81â5n2) for n=8â
2k, which is the best-known bound for Strassen-like multiplications. This paper proposes a method that reduces the complexity of Winograd's variant to (5n2.81+0.5n2.59+2n2.32â6.5n2) for n=2k. It is also shown that the total arithmetic complexity can be improved to (3.55n2.81+0.148n2.59+1.02n2.32â6.5n2) for n=8â
2k, which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Symbolic Computation - Volume 80, Part 2, MayâJune 2017, Pages 484-501
Journal: Journal of Symbolic Computation - Volume 80, Part 2, MayâJune 2017, Pages 484-501
نویسندگان
Murat Cenk, M. Anwar Hasan,