Алгоритм умножения матрицы квадратичной формы с разреженной матрицей
Я оптимизирую код, который в значительной степени опирается на пользовательскую библиотеку Matrix (которая не будет исключена из проекта, потому что она есть везде. Это нехорошо, но это факт...) Многие вычисления выполняются с помощью матриц из 10-20 строк и столбцов, многие вычисления включают в себя квадратичную форму, такую как
C = A*B*A'
Я понял, что часто А редок, и я хотел бы использовать этот факт. Поэтому я ищу алгоритм, который бы справился с этим делом. Численная стабильность важна. Есть ли что-нибудь, что я могу использовать? (Я не писал нашу библиотеку, поэтому я не знаю, есть ли какие-то подводные камни, которые я должен принять во внимание?)
Поскольку "наш" простой метод умножения O(n^3) выполняется быстрее, чем Eigen 3 на целевой платформе, поскольку мне нужна числовая стабильность, а матрицы не очень большие, я предполагаю, что алгоритм Штрассена, а также алгоритм Coppersmith–Winograd не то, что я ищу. Вместо этого это просто умножение квадратичных форм таким способом, который позволяет мне легко проверять нули в A.
Спасибо за любые предложения!
3 ответа
Есть способы реализовать разреженную матрицу таким образом, чтобы получить более сжатую, чем плотную матрицу. Один из способов сделать это заключается в следующем:
[0 0 0 0 0]
[0 1 2 0 9]
[0 0 0 2 0]
[0 1 0 0 0]
становится линейным массивом ненулевых элементов
typedef struct {
int row;
int col;
double entry;
} Element;
typedef SparseMatrix Element*;
Таким образом, матрица теперь имеет пространственную сложность O(n) вместо O(n^2). Для A*B, где A и B - матрицы, вам нужно только пройти каждый массив для сопоставления элементов (т.е. a->row == b->col && a->col == b->row), и, возможно, добавьте несколько вместе (внутренний продукт). Этот алгоритм будет иметь сложность O(n^2), а не O(n^3). Это потому, что вы можете пропустить легкомысленную операцию по взятию внутреннего продукта, который приведет к нулю.
Существует статья, посвященная быстрому разреженному матричному умножению. Разработанный алгоритм делит разреженную матрицу на две части: плотную и разреженную и применяет к ней алгоритм быстрого умножения. Так что для меня это выглядит так, что это зависит не от размера матрицы, как вы упомянули в отношении Штрассена, а от того, что она редкая.