We’re rewarding the question askers & reputations are being recalculated! Read more.

3 edited tags
2 added 287 characters in body

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.

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.