Как уменьшить количество умножений матриц
Позволять A быть заданной квадратной матрицей, размер которой nxn, Позволять A[i] обозначить nxn матрица, образованная заменой iстолбец A с нулевым вектором столбца.
Теперь я хочу рассчитать следующее (n^4+n^3+n^2) матричные продукты:
{A[x]*A[y]*A[z]*A[w] | for all x=1,...n , y=1,...,n , z=1,...n, and w=1,...,n}
{A[y]*A[z]*A[w] | for all y=1,...,n , z=1,...n, and w=1,...,n}
{A[z]*A[w] | for all z=1,...n, and w=1,...,n}
Если бы я рассчитывал каждый продукт наивно, это заняло бы O((n^4+n^3+n^2)*n^3) временная сложность (при условии, что матричное умножение требует O(n^3) время).
Тем не менее, я заметил, что есть много повторяющихся умножений, которые можно запомнить. Есть ли эффективный способ (например, DP), который может уменьшить количество умножений матриц как можно меньше?
2 ответа
Умножьте A[z] и A[w], пропуская столбец "0" в w на каждой итерации, а затем просто заполняя этот столбец нулями в ответе (или, если вы называете память, то ее уже 0 на дефолт). Это твоя проблема № 3
Теперь возьмите эту матрицу с нулевым столбцом (wth column) и умножьте на нее A[y], снова воспользовавшись тем, что тот же столбец равен нулю, и вы можете пропустить умножения. Теперь у вас есть #2.
Повторите это еще раз, умножив A[x] на этот результат, используя тот же столбец 0.
В целом это означает, что у вас всего 3 * (n-1)*n * (2n) = 6 * n^3 - 6 * n^2 умножений (если моя математика верна).
Первая - очевидная - оптимизация заключается в использовании результатов 3-го набора для расчета первого.
Второй, который приходит на ум, немного сложнее.
Позволять B[i] обозначить nxn 0-матрица с iстолбец заменен на iстолбец A (IOW B[i] = A - A[i]).
Затем переписать матричное произведение, используя закон распределения матриц [1], вот так.A[x]*A[y] = (A - B[x])(A - B[y]) = (A - B[x])A - (A - B[x])B[y] = AA - B[x]A - AB[y] - B[x]B[y],
поскольку B[i] являются разреженными матрицами только с одним ненулевым столбцом, приведенные выше продукты очень легко вычислить, плюс одно "полное" умножение матриц - AA - нужно рассчитывать только один раз.
Случай 3-умножения будет выглядеть следующим образом.A[x]*A[y]*A[z] = AAA - B[x]AA - AB[y]A + B[x]B[y]A - AAB[z] + B[x]AB[z] + AB[y]B[z] + B[x]B[y]B[z],
После предыдущего шага у нас уже есть большинство факторов (каждый B[i]A а также AB[i]), если память не имеет значения; или мы можем легко вычислить его (так как, еще раз, B[i] редки).
Случай 4-умножения может быть затем выполнен аналогами.