эффективное вычисление трассировки (AB^{-1}) при заданных A и B

У меня есть две квадратные матрицы A и B. A симметрична, B симметрична положительно определенная. Я хотел бы вычислить $trace (A. B^{-1})$. Для Теперь, я вычислить разложение Холецкого Б, решить для C в уравнении $А=С. Б$ и суммирования диагональных элементов.

Существует ли более эффективный способ продолжения работы?

Я планирую использовать Eigen. Не могли бы вы предоставить реализацию, если матрицы разрежены (A часто может быть диагональным, B часто диагональным по полосе)?

2 6
matrix eigen

2 ответа:

Если B разрежен, то он может быть эффективным(т. е., O (n), предполагая хорошее число условий B) для решения для x_i в 

B x_i = a_i

(пример сопряженного градиентного кода приведен в Википедии). Принимая a_i за векторы столбцов A, Вы получаете матрицу B^{-1} A в O(n^2). Затем вы можете суммировать диагональные элементы, чтобы получить трассировку. Как правило, проще выполнить это разреженное обратное умножение, чем получить полный набор собственных значений. Для сравнения, Холецкого разложение равно O (n^3). (см. комментарий Даррена Энгвирды ниже о Холески ).

Если вам нужно только приближение к следу, вы можете фактически уменьшить стоимость до O (q n) путем усреднения 

r^T (A B^{-1}) r

Над q случайными векторами r. Обычно q << n. Это несмещенная оценка при условии, что компоненты случайного вектора r удовлетворяют 

< r_i r_j > = \delta_{ij}

Где < ... > обозначает среднее значение по распределению r. Например, компоненты r_i может быть независимым гауссовским распределением с единичной дисперсией. Или они могут быть выбраны равномерно из +-1. Обычно трассировка масштабируется как O(n) и ошибка в оценках трассировки масштабируется как O(sqrt(n/q)), поэтому относительная ошибка масштабируется как O(sqrt (1/nq)).

5

Если обобщенные собственные значения более эффективны для вычисления, вы можете вычислить обобщенные собственные значения, A*v = lambda* B *v, а затем суммировать все лямбды.

1