[線代] Strassen演算法

看板Math作者 (sarsaparilla)時間6年前 (2019/08/12 17:33), 6年前編輯推噓5(5推 0噓 17→)
留言22則, 4人參與, 6年前最新討論串1/1
矩陣乘法的一個演算法 把乘法跟加分的做組合 加快運算速度 好奇當初是怎麼想到的？ 是否有多個乘法與加分的算式 也都可以進一步優化？ 有訣竅嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.28.75.7 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1565602415.A.F50.html
推
08/12 19:11, 6年前 , 1F
觀察到大矩陣乘法運算慢，小矩陣乘法運算快。就將
08/12 19:11, 1F
→
08/12 19:12, 6年前 , 2F
矩陣切割。每次切對半，所以會要求邊長為2^n*2^n
08/12 19:12, 2F
→
08/12 19:13, 6年前 , 3F
這和微積分一樣，曲線下的面積不會算，就切割成很多
08/12 19:13, 3F
→
08/12 19:14, 6年前 , 4F
小份。數學方法不外乎分析、歸納，由小到大，由大到
08/12 19:14, 4F
→
08/12 19:15, 6年前 , 5F
小，由具體而抽象，由抽象而具體，由例子而通則，由
08/12 19:15, 5F
→
08/12 19:16, 6年前 , 6F
則而實例、遞迴，離散到連續，連續到離散，低維
08/12 19:16, 6F
→
08/12 19:16, 6年前 , 7F
到高維，高維到低維。你要不同的算法
08/12 19:16, 7F
→
08/12 19:17, 6年前 , 8F
子空間到全體，全體到延拓等等。
08/12 19:17, 8F
→
08/12 19:19, 6年前 , 9F
有序、選擇、遞迴等。而且擴展到所有學術的各層面。
08/12 19:19, 9F
→
08/12 19:20, 6年前 , 10F
比如說近體詩的平仄，也可以看成布林代數的排列。
08/12 19:20, 10F
推
08/12 19:25, 6年前 , 11F
程式都是一步驟一步驟解決，或呼叫函式。其他的優化
08/12 19:25, 11F
→
08/12 19:25, 6年前 , 12F
要查文章。
08/12 19:25, 12F
→
08/12 19:43, 6年前 , 13F
乘法有karatsuba
08/12 19:43, 13F
好的 感謝 我會再想一想查資料 最近覺得這蠻有趣的 ※ 編輯: loadingN (110.28.75.7 臺灣), 08/12/2019 23:10:58
推
08/12 23:49, 6年前 , 14F
Coppersmith–Winograd algorithm 是一個比較快但實
08/12 23:49, 14F
→
08/12 23:50, 6年前 , 15F
用性不高的方法，看影片介紹就覺得很複雜，
08/12 23:50, 15F
→
08/12 23:50, 6年前 , 16F
Strassen演算法應該算滿主要的方法。
08/12 23:50, 16F
推
08/13 06:28, 6年前 , 17F
要說乘加法的運算式的話, 最近很夯的 AI 領域
08/13 06:28, 17F
→
08/13 06:29, 6年前 , 18F
其底層的核心運算卷積乘法也是有類似的演算法研究在
08/13 06:29, 18F
→
08/13 06:33, 6年前 , 19F
有看過的例如 Winograd convolution algorithm
08/13 06:33, 19F
→
08/13 06:33, 6年前 , 20F
(和上面 chem 大提的演算法名字裡的 Winograd
08/13 06:33, 20F
→
08/13 06:34, 6年前 , 21F
應該是同一個人 XD) 用來減少 3x3 卷積的乘法數
08/13 06:34, 21F
推
08/14 09:32, 6年前 , 22F
太神啦
08/14 09:32, 22F
‣ 更多 loadingN 的文章
文章代碼(AID): #1TKJ9lzG (Math)