任意矩阵乘法的复杂性 [英] Complexity of arbitrary matrix multiplications

问题描述

我有关于矩阵乘法的实现一个简单的问题。我知道有同等大小（n×n个）具有的为O（n ^ 2.xxx）复杂的矩阵算法。但是，如果我有两个矩阵A和不同大小的B（PXQ，qxr），这将是实施日期的最小的复杂性？我猜想它是O（PQR），因为我想实现一个乘法3嵌套循环使用P，Q和R迭代。特别是，有没有人现在怎么样了征库实现乘法？

I've got a simple question concerning the implementation of matrix multiplications. I know that there are algorithms for matrices of equal size (n x n) that have a complexity of O(n^2.xxx). But if I have two matrices A and B of different sizes (p x q, q x r), what would be the minimal complexity of the implementation to date? I would guess it is O(pqr) since I would implement a multiplication with 3 nested loops with p, q and r iterations. In particular, does anyone now how the Eigen library implements a multiplication?

推荐答案

一个常见的​​技术是垫矩阵大小为（P * Q，Q * R），使它们的尺寸为（N * N）。然后，你可以申请Strassen的算法。

A common technique is to pad matrices with size (p*q, q*r), so that their sizes becomes (n*n). Then, you can apply Strassen's algorithm.

这篇关于任意矩阵乘法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！