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

Question

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

Есть ли более эффективный способ продолжить?

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

Answer 1

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

B x_i = a_i

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

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

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)).

Answer 2

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