We’re rewarding the question askers & reputations are being recalculated! Read more.
3 edited tags
| link
2 added 287 characters in body
source | link

Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices?

For example, if each $D_i$ is scalar, it suffices to compute the SVD of $A$. However, this breaks down for general $D$ due to lack of commutativity.

Update: The answers so far are "no". Does anyone have any interesting intuition as to why? A no answer means that there's no nontrivial way to compress the information between two noncommuting operators. It isn't terribly surprisingly, but it'd be great to understand it better.

Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices?

For example, if each $D_i$ is scalar, it suffices to compute the SVD of $A$. However, this breaks down for general $D$ due to lack of commutativity.

Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices?

For example, if each $D_i$ is scalar, it suffices to compute the SVD of $A$. However, this breaks down for general $D$ due to lack of commutativity.

Update: The answers so far are "no". Does anyone have any interesting intuition as to why? A no answer means that there's no nontrivial way to compress the information between two noncommuting operators. It isn't terribly surprisingly, but it'd be great to understand it better.

    Tweeted twitter.com/#!/StackSciComp/status/149722328778018816
1
source | link

Can diagonal plus fixed symmetric linear systems be solved in quadratic time after precomputation?

Is there an $O(n^3+n^2 k)$ method to solve $k$ linear systems of the form $(D_i + A) x_i = b_i$ where $A$ is a fixed SPD matrix and $D_i$ are positive diagonal matrices?

For example, if each $D_i$ is scalar, it suffices to compute the SVD of $A$. However, this breaks down for general $D$ due to lack of commutativity.