矩陣與向量相乘有沒有快速演算法？
雖然直覺上認為A*x這樣的運算應該沒有捷徑可走，但還是抱著一絲渺茫的希望來問各位大神；一個m*n的矩陣A與一個n維的列向量x相乘，在m和n很大的條件下，是否存在比按定義算更快速的演算法？還望各位大牛不吝賜教。感謝！
按照定義算複雜度已經是 O(mn) 了，A 一共有 mn 個元素，你總需要把所有元素訪問一遍吧。除非 A 存在某些已知的特殊條件，例如稀疏或者對稱之類的，這種情況下可能降低理論複雜度。
不過即使是同樣的演算法，不同的實現性能也可能有很大差別，例如你手寫的 naive 實現一般要慢於 openBLAS 或 MKL 之類的高度優化的緩存友好且針對特定硬體和向量化指令集優化的實現。
在硬體上，使用 GPU 或者某些專用的加速器（協處理器）也是一種選擇。
直接算需要 次乘法和
次加法，約等於
次運算。
在矩陣和向量沒有特殊數字結構（比如稀疏陣、對角陣、含大量0的向量）時，光是把A的每個元素訪問一遍就是 了，所以必定是
級別的，最多就是優化下"2"這個係數。優化方式有三類：
1、並行運算。比如按行把矩陣分成k塊，k塊同時算，那麼時間上就縮短到了1/k.
2、從硬體著手，使用專門的硬體模塊。像顯卡GPU之類需要大量線性計算的地方就是這麼做的。
3、就像 以加代乘 的那個加速乘法演算法一樣，通過打包、FFT等方式嘗試降低係數，或者平衡快慢不同的運算方式的使用(訪問和運算速度的差異、考慮內存存儲的連續性、加乘異或操作代價不同等等)。——具體怎麼做我想不出來。
最直接想到的方法是設計 個並行程序計算這
個向量內積（矩陣
的所有行與
內積）的，而按照歐式空間內積的常用定義，它只是將兩個長度相同（假設為
）的向量對應元素相乘再相加，而內積又可以設計成並行的，也就是用 設計
個並行程序計算
次乘法，諸如此類的。
template&
inline std::array& matrix_vector_dot(const std::array&, M&> matrix,const std::array&v)
{
std::array& result;
std::transform(matrix.begin(), matrix.end(), result.begin(), [v](auto e){
return std::transform_reduce(e.begin(), e.end(), v.begin(), 0);
});
return result;
}
普通的C++ STL寫法，我只想說和C語言寫法沒有效率差距吧，歡迎測試。
演算法上不存在。可以向量化，堆硬體加速。
有
設計一個專門計算矩陣*向量的CPU
推薦閱讀：
