矩阵与向量相乘有没有快速演算法？
虽然直觉上认为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
推荐阅读：
