Алгоритм умножения матрицы квадратичной формы с разреженной матрицей

Question

Я оптимизирую код, который в значительной степени опирается на пользовательскую библиотеку Matrix (которая не будет исключена из проекта, потому что она есть везде. Это нехорошо, но это факт ...) Многие вычисления выполняются с помощью матриц из 10-20 строк и столбцов многие вычисления включают в себя квадратичную форму, например

 C = A*B*A'

Я понял, что часто А редок, и я хотел бы использовать этот факт. Поэтому я ищу алгоритм, который бы справился с этим делом. Численная стабильность важна. Я могу что-нибудь использовать? (Я не писал нашу библиотеку, поэтому я не знаю, есть ли какие-то подводные камни, которые я должен принять во внимание?)

Поскольку «наш» простой метод умножения O (n ^ 3) выполняется быстрее, чем Eigen 3 на целевой платформе, поскольку мне нужна числовая стабильность, а матрицы не очень большие, я полагаю, что алгоритм Штрассена так же, как и Coppersmith– Виноградный алгоритм - это не то, что я ищу. Вместо этого это просто умножение квадратичных форм таким способом, который позволяет мне легко проверять нули в A.

Спасибо за любые предложения!

Answer 1

Есть способы реализовать разреженную матрицу таким образом, чтобы получить более сжатую, чем плотную матрицу. Один из способов сделать это следующим образом:

[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 - матрицы, вам нужно только пройти через каждый массив для сопоставления элементов (т.е. несколько вместе (внутренний продукт). Этот алгоритм будет иметь сложность O (n ^ 2), а не O (n ^ 3). Это потому, что вы можете пропустить легкомысленную операцию по взятию внутреннего продукта, которая приведет к нулю.

Answer 2

проверить Алгоритм высокопараллельного разреженного матрично-матричного умножения

Answer 3

Существует эта статья, посвященная быстрому умножению на разреженные матрицы.Разработанный алгоритм делит разреженную матрицу на две части: плотную и разреженную и применяет к ней алгоритм быстрого умножения.Поэтому для меня это выглядит так, что это зависит не от размера матрицы, как вы упомянули в отношении Штрассена, а от того, что она редкая.