Calculating the diagonal of $(I-Q)^{-1}$ efficiently
$begingroup$
Motivation: I'm trying to write code to solve an equation efficiently. Directly calculating the result is easy, but involves matrix inversions that consume an impractical amount of memory at the scale we want (think 1,000,000 x 1,000,000 matrices). The actual input matrix is sparse, so avoiding the inverse potentially makes it practical. I've managed to reformulate the problem into $xA=B$ form, which has worked for me at the scale I want with other equations.
The problem is that the reformulation still has one last inversion that I can't figure out how to deal with. Currently:
$$A=diagBigl((I-Q)^{-1}Bigr)(I-Q)$$
$$B=vQ$$
$x$ and $v$ are vectors. $Q$ is a sparse square matrix with a diagonal of $[0]$ and a few superdiagonals and subdiagonals. The structure of the matrix is symmetric, but the values are not. The values are in the interval $[0,1]$, with each row summing to $le1$.
I've tried to find solutions that allow me to calculate just the diagonal of the inverse, but the solutions I've found seem to require matrix properties (particularly symmetry) that mine does not. I've also been trying to express the $(I-Q)^{-1}$ in different forms to see if there are other properties of my matrix that I can take advantage of. For example, on the Woodbury matrix identity wikipedia page I found the special case of $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}$$ which, when $A=I$, simplifies to $$=sum_{k=0}^infty B^k$$
Neat, but I have no idea if it helps me though.
I also saw this interesting post on this forum, which had me excited until I realized the condition of $Q^3 = [0]$ doesn't apply to me.
So does anyone have any thoughts for how I can avoid calculating the full inverse in $A$ up above? I included the other terms of the equation in case it is helpful. I tried my best to use terminology correctly and display things appropriately, but this level of linear algebra is completely new to me.
linear-algebra matrices inverse
asked Dec 19 '18 at 16:23
anjamaanjama
233
$endgroup$
add a comment |
$begingroup$
Motivation: I'm trying to write code to solve an equation efficiently. Directly calculating the result is easy, but involves matrix inversions that consume an impractical amount of memory at the scale we want (think 1,000,000 x 1,000,000 matrices). The actual input matrix is sparse, so avoiding the inverse potentially makes it practical. I've managed to reformulate the problem into $xA=B$ form, which has worked for me at the scale I want with other equations.
The problem is that the reformulation still has one last inversion that I can't figure out how to deal with. Currently:
$$A=diagBigl((I-Q)^{-1}Bigr)(I-Q)$$
$$B=vQ$$
$x$ and $v$ are vectors. $Q$ is a sparse square matrix with a diagonal of $[0]$ and a few superdiagonals and subdiagonals. The structure of the matrix is symmetric, but the values are not. The values are in the interval $[0,1]$, with each row summing to $le1$.
I've tried to find solutions that allow me to calculate just the diagonal of the inverse, but the solutions I've found seem to require matrix properties (particularly symmetry) that mine does not. I've also been trying to express the $(I-Q)^{-1}$ in different forms to see if there are other properties of my matrix that I can take advantage of. For example, on the Woodbury matrix identity wikipedia page I found the special case of $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}$$ which, when $A=I$, simplifies to $$=sum_{k=0}^infty B^k$$
Neat, but I have no idea if it helps me though.
I also saw this interesting post on this forum, which had me excited until I realized the condition of $Q^3 = [0]$ doesn't apply to me.
So does anyone have any thoughts for how I can avoid calculating the full inverse in $A$ up above? I included the other terms of the equation in case it is helpful. I tried my best to use terminology correctly and display things appropriately, but this level of linear algebra is completely new to me.
linear-algebra matrices inverse
asked Dec 19 '18 at 16:23
anjamaanjama
233
$endgroup$
$begingroup$
Do you need an exact solution? If not, try expanding $(I-Q)^{-1}$ as a truncated power series.
$endgroup$
– amd
Dec 19 '18 at 20:36
$begingroup$
@amd I'm experimenting with it as an intermediate solution, but it appears that as the matrices get larger, more iterations are needed to maintain an acceptable level of precision, and that higher iterations results in increasingly less sparse matrices. So it might not be a huge benefit past what can already be accomplished by direct calculation.
$endgroup$
– anjama
Dec 20 '18 at 2:31
1
$begingroup$
Diagonalization/Jordan normal form makes the power series easier to compute and control.
$endgroup$
– amd
Dec 20 '18 at 9:32
$begingroup$
In order to compute the diagonal of the inverse, you'd need to factorize the matrix and do the solve for all columns of the identity. I remember this paper was dealing with reducing the number of solves by inspecting the sparsity pattern of the matrix.
$endgroup$
– Algebraic Pavel
Dec 21 '18 at 11:29
$begingroup$
@amd With the test cases I've tried so far, it appears my matrices are diagonalizable where $B=PDP^{-1}$. And then I'm able to efficiently calculate the power series for $D_{ii}$ using $1/(1-D_{ii})$, but I'm stuck with needing $P$ and $P^{-1}$, which are dense matrices, putting me back in my original situation at larger scales. Is there a way to factor out the need for them in $diag(PDP^{-1})$?
$endgroup$
– anjama
Dec 21 '18 at 15:17
add a comment |
$begingroup$
Motivation: I'm trying to write code to solve an equation efficiently. Directly calculating the result is easy, but involves matrix inversions that consume an impractical amount of memory at the scale we want (think 1,000,000 x 1,000,000 matrices). The actual input matrix is sparse, so avoiding the inverse potentially makes it practical. I've managed to reformulate the problem into $xA=B$ form, which has worked for me at the scale I want with other equations.
The problem is that the reformulation still has one last inversion that I can't figure out how to deal with. Currently:
$$A=diagBigl((I-Q)^{-1}Bigr)(I-Q)$$
$$B=vQ$$
$x$ and $v$ are vectors. $Q$ is a sparse square matrix with a diagonal of $[0]$ and a few superdiagonals and subdiagonals. The structure of the matrix is symmetric, but the values are not. The values are in the interval $[0,1]$, with each row summing to $le1$.
I've tried to find solutions that allow me to calculate just the diagonal of the inverse, but the solutions I've found seem to require matrix properties (particularly symmetry) that mine does not. I've also been trying to express the $(I-Q)^{-1}$ in different forms to see if there are other properties of my matrix that I can take advantage of. For example, on the Woodbury matrix identity wikipedia page I found the special case of $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}$$ which, when $A=I$, simplifies to $$=sum_{k=0}^infty B^k$$
Neat, but I have no idea if it helps me though.
I also saw this interesting post on this forum, which had me excited until I realized the condition of $Q^3 = [0]$ doesn't apply to me.
So does anyone have any thoughts for how I can avoid calculating the full inverse in $A$ up above? I included the other terms of the equation in case it is helpful. I tried my best to use terminology correctly and display things appropriately, but this level of linear algebra is completely new to me.
linear-algebra matrices inverse
asked Dec 19 '18 at 16:23
anjamaanjama
233
$endgroup$
Motivation: I'm trying to write code to solve an equation efficiently. Directly calculating the result is easy, but involves matrix inversions that consume an impractical amount of memory at the scale we want (think 1,000,000 x 1,000,000 matrices). The actual input matrix is sparse, so avoiding the inverse potentially makes it practical. I've managed to reformulate the problem into $xA=B$ form, which has worked for me at the scale I want with other equations.
The problem is that the reformulation still has one last inversion that I can't figure out how to deal with. Currently:
$$A=diagBigl((I-Q)^{-1}Bigr)(I-Q)$$
$$B=vQ$$
$x$ and $v$ are vectors. $Q$ is a sparse square matrix with a diagonal of $[0]$ and a few superdiagonals and subdiagonals. The structure of the matrix is symmetric, but the values are not. The values are in the interval $[0,1]$, with each row summing to $le1$.
I've tried to find solutions that allow me to calculate just the diagonal of the inverse, but the solutions I've found seem to require matrix properties (particularly symmetry) that mine does not. I've also been trying to express the $(I-Q)^{-1}$ in different forms to see if there are other properties of my matrix that I can take advantage of. For example, on the Woodbury matrix identity wikipedia page I found the special case of $$(A-B)^{-1}=sum_{k=0}^infty (A^{-1}B)^{k}A^{-1}$$ which, when $A=I$, simplifies to $$=sum_{k=0}^infty B^k$$
Neat, but I have no idea if it helps me though.
I also saw this interesting post on this forum, which had me excited until I realized the condition of $Q^3 = [0]$ doesn't apply to me.
So does anyone have any thoughts for how I can avoid calculating the full inverse in $A$ up above? I included the other terms of the equation in case it is helpful. I tried my best to use terminology correctly and display things appropriately, but this level of linear algebra is completely new to me.
linear-algebra matrices inverse
linear-algebra matrices inverse
asked Dec 19 '18 at 16:23
anjamaanjama
233
asked Dec 19 '18 at 16:23
anjamaanjama
233
edited Dec 20 '18 at 14:39
anjama
asked Dec 19 '18 at 16:23
anjamaanjama
233
asked Dec 19 '18 at 16:23
anjamaanjama
233
asked Dec 19 '18 at 16:23
anjamaanjama
233
233
$begingroup$
Do you need an exact solution? If not, try expanding $(I-Q)^{-1}$ as a truncated power series.
$endgroup$
– amd
Dec 19 '18 at 20:36
$begingroup$
@amd I'm experimenting with it as an intermediate solution, but it appears that as the matrices get larger, more iterations are needed to maintain an acceptable level of precision, and that higher iterations results in increasingly less sparse matrices. So it might not be a huge benefit past what can already be accomplished by direct calculation.
$endgroup$
– anjama
Dec 20 '18 at 2:31
1
$begingroup$
Diagonalization/Jordan normal form makes the power series easier to compute and control.
$endgroup$
– amd
Dec 20 '18 at 9:32
$begingroup$
In order to compute the diagonal of the inverse, you'd need to factorize the matrix and do the solve for all columns of the identity. I remember this paper was dealing with reducing the number of solves by inspecting the sparsity pattern of the matrix.
$endgroup$
– Algebraic Pavel
Dec 21 '18 at 11:29
$begingroup$
@amd With the test cases I've tried so far, it appears my matrices are diagonalizable where $B=PDP^{-1}$. And then I'm able to efficiently calculate the power series for $D_{ii}$ using $1/(1-D_{ii})$, but I'm stuck with needing $P$ and $P^{-1}$, which are dense matrices, putting me back in my original situation at larger scales. Is there a way to factor out the need for them in $diag(PDP^{-1})$?
$endgroup$
– anjama
Dec 21 '18 at 15:17
add a comment |
$begingroup$
Do you need an exact solution? If not, try expanding $(I-Q)^{-1}$ as a truncated power series.
$endgroup$
– amd
Dec 19 '18 at 20:36
$begingroup$
@amd I'm experimenting with it as an intermediate solution, but it appears that as the matrices get larger, more iterations are needed to maintain an acceptable level of precision, and that higher iterations results in increasingly less sparse matrices. So it might not be a huge benefit past what can already be accomplished by direct calculation.
$endgroup$
– anjama
Dec 20 '18 at 2:31
1
$begingroup$
Diagonalization/Jordan normal form makes the power series easier to compute and control.
$endgroup$
– amd
Dec 20 '18 at 9:32
$begingroup$
In order to compute the diagonal of the inverse, you'd need to factorize the matrix and do the solve for all columns of the identity. I remember this paper was dealing with reducing the number of solves by inspecting the sparsity pattern of the matrix.
$endgroup$
– Algebraic Pavel
Dec 21 '18 at 11:29
$begingroup$
@amd With the test cases I've tried so far, it appears my matrices are diagonalizable where $B=PDP^{-1}$. And then I'm able to efficiently calculate the power series for $D_{ii}$ using $1/(1-D_{ii})$, but I'm stuck with needing $P$ and $P^{-1}$, which are dense matrices, putting me back in my original situation at larger scales. Is there a way to factor out the need for them in $diag(PDP^{-1})$?
$endgroup$
– anjama
Dec 21 '18 at 15:17
$begingroup$
Do you need an exact solution? If not, try expanding $(I-Q)^{-1}$ as a truncated power series.
$endgroup$
– amd
Dec 19 '18 at 20:36
$begingroup$
Do you need an exact solution? If not, try expanding $(I-Q)^{-1}$ as a truncated power series.
$endgroup$
– amd
Dec 19 '18 at 20:36
$begingroup$
@amd I'm experimenting with it as an intermediate solution, but it appears that as the matrices get larger, more iterations are needed to maintain an acceptable level of precision, and that higher iterations results in increasingly less sparse matrices. So it might not be a huge benefit past what can already be accomplished by direct calculation.
$endgroup$
– anjama
Dec 20 '18 at 2:31
$begingroup$
@amd I'm experimenting with it as an intermediate solution, but it appears that as the matrices get larger, more iterations are needed to maintain an acceptable level of precision, and that higher iterations results in increasingly less sparse matrices. So it might not be a huge benefit past what can already be accomplished by direct calculation.
$endgroup$
– anjama
Dec 20 '18 at 2:31
1
1
$begingroup$
Diagonalization/Jordan normal form makes the power series easier to compute and control.
$endgroup$
– amd
Dec 20 '18 at 9:32
$begingroup$
Diagonalization/Jordan normal form makes the power series easier to compute and control.
$endgroup$
– amd
Dec 20 '18 at 9:32
$begingroup$
In order to compute the diagonal of the inverse, you'd need to factorize the matrix and do the solve for all columns of the identity. I remember this paper was dealing with reducing the number of solves by inspecting the sparsity pattern of the matrix.
$endgroup$
– Algebraic Pavel
Dec 21 '18 at 11:29
$begingroup$
In order to compute the diagonal of the inverse, you'd need to factorize the matrix and do the solve for all columns of the identity. I remember this paper was dealing with reducing the number of solves by inspecting the sparsity pattern of the matrix.
$endgroup$
– Algebraic Pavel
Dec 21 '18 at 11:29
$begingroup$
@amd With the test cases I've tried so far, it appears my matrices are diagonalizable where $B=PDP^{-1}$. And then I'm able to efficiently calculate the power series for $D_{ii}$ using $1/(1-D_{ii})$, but I'm stuck with needing $P$ and $P^{-1}$, which are dense matrices, putting me back in my original situation at larger scales. Is there a way to factor out the need for them in $diag(PDP^{-1})$?
$endgroup$
– anjama
Dec 21 '18 at 15:17
$begingroup$
@amd With the test cases I've tried so far, it appears my matrices are diagonalizable where $B=PDP^{-1}$. And then I'm able to efficiently calculate the power series for $D_{ii}$ using $1/(1-D_{ii})$, but I'm stuck with needing $P$ and $P^{-1}$, which are dense matrices, putting me back in my original situation at larger scales. Is there a way to factor out the need for them in $diag(PDP^{-1})$?
$endgroup$
– anjama
Dec 21 '18 at 15:17
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3046574%2fcalculating-the-diagonal-of-i-q-1-efficiently%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3046574%2fcalculating-the-diagonal-of-i-q-1-efficiently%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Do you need an exact solution? If not, try expanding $(I-Q)^{-1}$ as a truncated power series.
$endgroup$
– amd
Dec 19 '18 at 20:36
$begingroup$
@amd I'm experimenting with it as an intermediate solution, but it appears that as the matrices get larger, more iterations are needed to maintain an acceptable level of precision, and that higher iterations results in increasingly less sparse matrices. So it might not be a huge benefit past what can already be accomplished by direct calculation.
$endgroup$
– anjama
Dec 20 '18 at 2:31
1
$begingroup$
Diagonalization/Jordan normal form makes the power series easier to compute and control.
$endgroup$
– amd
Dec 20 '18 at 9:32
$begingroup$
In order to compute the diagonal of the inverse, you'd need to factorize the matrix and do the solve for all columns of the identity. I remember this paper was dealing with reducing the number of solves by inspecting the sparsity pattern of the matrix.
$endgroup$
– Algebraic Pavel
Dec 21 '18 at 11:29
$begingroup$
@amd With the test cases I've tried so far, it appears my matrices are diagonalizable where $B=PDP^{-1}$. And then I'm able to efficiently calculate the power series for $D_{ii}$ using $1/(1-D_{ii})$, but I'm stuck with needing $P$ and $P^{-1}$, which are dense matrices, putting me back in my original situation at larger scales. Is there a way to factor out the need for them in $diag(PDP^{-1})$?
$endgroup$
– anjama
Dec 21 '18 at 15:17