What is the best algorithm to find the inverse of matrix $A$
$begingroup$
I'm going to build a C-library so I can do linear algebra at embedded systems. It's most for machine learning. https://github.com/DanielMartensson/EmbeddedAlgebra/
Anyway, I need to compute inverse of matrix $A$. What is the absolute best algorithm to use for that? Remember it must be a numerical algorithm.
Which one should I use?
Analytic solution
$mathbf{A}^{-1}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}mathbf{C}^{mathrm{T}}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}
begin{pmatrix}
mathbf{C}_{11} & mathbf{C}_{21} & cdots & mathbf{C}_{n1} \
mathbf{C}_{12} & mathbf{C}_{22} & cdots & mathbf{C}_{n2} \
vdots & vdots & ddots & vdots \
mathbf{C}_{1n} & mathbf{C}_{2n} & cdots & mathbf{C}_{nn} \
end{pmatrix}$
Cholesky decomposition
$mathbf{A}^{-1} = (mathbf{L}^{*})^{-1} mathbf{L}^{-1}$
Eigendecomposition
$mathbf{A}^{-1}=mathbf{Q}mathbf{Lambda}^{-1}mathbf{Q}^{-1}$
Cayley–Hamilton method
$mathbf{A}^{-1} = frac{1}{det (mathbf{A})}sum_{s=0}^{n-1}A^s$
Newton's method
$X_{k+1} = 2X_k - X_k A X_k$
Neuman series
$lim_{n to infty} (mathbf I - mathbf A)^n = 0$
Gaussian elimination
$A =
begin{bmatrix}
2 & -1 & 0 \
-1 & 2 & -1 \
0 & -1 & 2
end{bmatrix}$
To find the inverse of this matrix, one takes the following matrix augmented by the identity, and row reduces it as a 3 × 6 matrix:
$
[ A | I ] =
left[ begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\
-1 & 2 & -1 & 0 & 1 & 0\
0 & -1 & 2 & 0 & 0 & 1
end{array} right]$
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is:
$[ I | B ] =
left[ begin{array}{rrr|rrr}
1 & 0 & 0 & frac34 & frac12 & frac14\[3pt]
0 & 1 & 0 & frac12 & 1 & frac12\[3pt]
0 & 0 & 1 & frac14 & frac12 & frac34
end{array} right]$
matrices inverse numerical-linear-algebra
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
$endgroup$
|
show 4 more comments
$begingroup$
I'm going to build a C-library so I can do linear algebra at embedded systems. It's most for machine learning. https://github.com/DanielMartensson/EmbeddedAlgebra/
Anyway, I need to compute inverse of matrix $A$. What is the absolute best algorithm to use for that? Remember it must be a numerical algorithm.
Which one should I use?
Analytic solution
$mathbf{A}^{-1}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}mathbf{C}^{mathrm{T}}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}
begin{pmatrix}
mathbf{C}_{11} & mathbf{C}_{21} & cdots & mathbf{C}_{n1} \
mathbf{C}_{12} & mathbf{C}_{22} & cdots & mathbf{C}_{n2} \
vdots & vdots & ddots & vdots \
mathbf{C}_{1n} & mathbf{C}_{2n} & cdots & mathbf{C}_{nn} \
end{pmatrix}$
Cholesky decomposition
$mathbf{A}^{-1} = (mathbf{L}^{*})^{-1} mathbf{L}^{-1}$
Eigendecomposition
$mathbf{A}^{-1}=mathbf{Q}mathbf{Lambda}^{-1}mathbf{Q}^{-1}$
Cayley–Hamilton method
$mathbf{A}^{-1} = frac{1}{det (mathbf{A})}sum_{s=0}^{n-1}A^s$
Newton's method
$X_{k+1} = 2X_k - X_k A X_k$
Neuman series
$lim_{n to infty} (mathbf I - mathbf A)^n = 0$
Gaussian elimination
$A =
begin{bmatrix}
2 & -1 & 0 \
-1 & 2 & -1 \
0 & -1 & 2
end{bmatrix}$
To find the inverse of this matrix, one takes the following matrix augmented by the identity, and row reduces it as a 3 × 6 matrix:
$
[ A | I ] =
left[ begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\
-1 & 2 & -1 & 0 & 1 & 0\
0 & -1 & 2 & 0 & 0 & 1
end{array} right]$
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is:
$[ I | B ] =
left[ begin{array}{rrr|rrr}
1 & 0 & 0 & frac34 & frac12 & frac14\[3pt]
0 & 1 & 0 & frac12 & 1 & frac12\[3pt]
0 & 0 & 1 & frac14 & frac12 & frac34
end{array} right]$
matrices inverse numerical-linear-algebra
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
$endgroup$
5
$begingroup$
As a non-mathematical comment: for the love of god, don't. Firstly, you probably don't want to invert a matrix at all (see, for example, here). Secondly, use one of the many impementations that already exist.
$endgroup$
– user3482749
Jan 11 at 20:16
$begingroup$
So what should I do?
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:24
$begingroup$
In almost all cases, you should just solve $Ax = b$, since that's probably what you want to do anyway, and it's vastly quicker than computing $A^{-1}$ then calculating $A^{-1}b$ (indeed, it's quicker than either of those steps alone). If you really must invert $A$, just use one of the implementations that already exist in other people's algorithms.
$endgroup$
– user3482749
Jan 11 at 21:33
1
$begingroup$
See here. The correct, answer, however, is almost certainly "just use somebody else's solution".
$endgroup$
– user3482749
Jan 11 at 22:35
1
$begingroup$
All six of them are in C.
$endgroup$
– user3482749
Jan 12 at 11:27
|
show 4 more comments
$begingroup$
I'm going to build a C-library so I can do linear algebra at embedded systems. It's most for machine learning. https://github.com/DanielMartensson/EmbeddedAlgebra/
Anyway, I need to compute inverse of matrix $A$. What is the absolute best algorithm to use for that? Remember it must be a numerical algorithm.
Which one should I use?
Analytic solution
$mathbf{A}^{-1}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}mathbf{C}^{mathrm{T}}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}
begin{pmatrix}
mathbf{C}_{11} & mathbf{C}_{21} & cdots & mathbf{C}_{n1} \
mathbf{C}_{12} & mathbf{C}_{22} & cdots & mathbf{C}_{n2} \
vdots & vdots & ddots & vdots \
mathbf{C}_{1n} & mathbf{C}_{2n} & cdots & mathbf{C}_{nn} \
end{pmatrix}$
Cholesky decomposition
$mathbf{A}^{-1} = (mathbf{L}^{*})^{-1} mathbf{L}^{-1}$
Eigendecomposition
$mathbf{A}^{-1}=mathbf{Q}mathbf{Lambda}^{-1}mathbf{Q}^{-1}$
Cayley–Hamilton method
$mathbf{A}^{-1} = frac{1}{det (mathbf{A})}sum_{s=0}^{n-1}A^s$
Newton's method
$X_{k+1} = 2X_k - X_k A X_k$
Neuman series
$lim_{n to infty} (mathbf I - mathbf A)^n = 0$
Gaussian elimination
$A =
begin{bmatrix}
2 & -1 & 0 \
-1 & 2 & -1 \
0 & -1 & 2
end{bmatrix}$
To find the inverse of this matrix, one takes the following matrix augmented by the identity, and row reduces it as a 3 × 6 matrix:
$
[ A | I ] =
left[ begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\
-1 & 2 & -1 & 0 & 1 & 0\
0 & -1 & 2 & 0 & 0 & 1
end{array} right]$
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is:
$[ I | B ] =
left[ begin{array}{rrr|rrr}
1 & 0 & 0 & frac34 & frac12 & frac14\[3pt]
0 & 1 & 0 & frac12 & 1 & frac12\[3pt]
0 & 0 & 1 & frac14 & frac12 & frac34
end{array} right]$
matrices inverse numerical-linear-algebra
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
$endgroup$
I'm going to build a C-library so I can do linear algebra at embedded systems. It's most for machine learning. https://github.com/DanielMartensson/EmbeddedAlgebra/
Anyway, I need to compute inverse of matrix $A$. What is the absolute best algorithm to use for that? Remember it must be a numerical algorithm.
Which one should I use?
Analytic solution
$mathbf{A}^{-1}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}mathbf{C}^{mathrm{T}}={1 over begin{vmatrix}mathbf{A}end{vmatrix}}
begin{pmatrix}
mathbf{C}_{11} & mathbf{C}_{21} & cdots & mathbf{C}_{n1} \
mathbf{C}_{12} & mathbf{C}_{22} & cdots & mathbf{C}_{n2} \
vdots & vdots & ddots & vdots \
mathbf{C}_{1n} & mathbf{C}_{2n} & cdots & mathbf{C}_{nn} \
end{pmatrix}$
Cholesky decomposition
$mathbf{A}^{-1} = (mathbf{L}^{*})^{-1} mathbf{L}^{-1}$
Eigendecomposition
$mathbf{A}^{-1}=mathbf{Q}mathbf{Lambda}^{-1}mathbf{Q}^{-1}$
Cayley–Hamilton method
$mathbf{A}^{-1} = frac{1}{det (mathbf{A})}sum_{s=0}^{n-1}A^s$
Newton's method
$X_{k+1} = 2X_k - X_k A X_k$
Neuman series
$lim_{n to infty} (mathbf I - mathbf A)^n = 0$
Gaussian elimination
$A =
begin{bmatrix}
2 & -1 & 0 \
-1 & 2 & -1 \
0 & -1 & 2
end{bmatrix}$
To find the inverse of this matrix, one takes the following matrix augmented by the identity, and row reduces it as a 3 × 6 matrix:
$
[ A | I ] =
left[ begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\
-1 & 2 & -1 & 0 & 1 & 0\
0 & -1 & 2 & 0 & 0 & 1
end{array} right]$
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is:
$[ I | B ] =
left[ begin{array}{rrr|rrr}
1 & 0 & 0 & frac34 & frac12 & frac14\[3pt]
0 & 1 & 0 & frac12 & 1 & frac12\[3pt]
0 & 0 & 1 & frac14 & frac12 & frac34
end{array} right]$
matrices inverse numerical-linear-algebra
matrices inverse numerical-linear-algebra
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
asked Jan 11 at 20:03
Daniel MårtenssonDaniel Mårtensson
993419
993419
5
$begingroup$
As a non-mathematical comment: for the love of god, don't. Firstly, you probably don't want to invert a matrix at all (see, for example, here). Secondly, use one of the many impementations that already exist.
$endgroup$
– user3482749
Jan 11 at 20:16
$begingroup$
So what should I do?
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:24
$begingroup$
In almost all cases, you should just solve $Ax = b$, since that's probably what you want to do anyway, and it's vastly quicker than computing $A^{-1}$ then calculating $A^{-1}b$ (indeed, it's quicker than either of those steps alone). If you really must invert $A$, just use one of the implementations that already exist in other people's algorithms.
$endgroup$
– user3482749
Jan 11 at 21:33
1
$begingroup$
See here. The correct, answer, however, is almost certainly "just use somebody else's solution".
$endgroup$
– user3482749
Jan 11 at 22:35
1
$begingroup$
All six of them are in C.
$endgroup$
– user3482749
Jan 12 at 11:27
|
show 4 more comments
5
$begingroup$
As a non-mathematical comment: for the love of god, don't. Firstly, you probably don't want to invert a matrix at all (see, for example, here). Secondly, use one of the many impementations that already exist.
$endgroup$
– user3482749
Jan 11 at 20:16
$begingroup$
So what should I do?
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:24
$begingroup$
In almost all cases, you should just solve $Ax = b$, since that's probably what you want to do anyway, and it's vastly quicker than computing $A^{-1}$ then calculating $A^{-1}b$ (indeed, it's quicker than either of those steps alone). If you really must invert $A$, just use one of the implementations that already exist in other people's algorithms.
$endgroup$
– user3482749
Jan 11 at 21:33
1
$begingroup$
See here. The correct, answer, however, is almost certainly "just use somebody else's solution".
$endgroup$
– user3482749
Jan 11 at 22:35
1
$begingroup$
All six of them are in C.
$endgroup$
– user3482749
Jan 12 at 11:27
5
5
$begingroup$
As a non-mathematical comment: for the love of god, don't. Firstly, you probably don't want to invert a matrix at all (see, for example, here). Secondly, use one of the many impementations that already exist.
$endgroup$
– user3482749
Jan 11 at 20:16
$begingroup$
As a non-mathematical comment: for the love of god, don't. Firstly, you probably don't want to invert a matrix at all (see, for example, here). Secondly, use one of the many impementations that already exist.
$endgroup$
– user3482749
Jan 11 at 20:16
$begingroup$
So what should I do?
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:24
$begingroup$
So what should I do?
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:24
$begingroup$
In almost all cases, you should just solve $Ax = b$, since that's probably what you want to do anyway, and it's vastly quicker than computing $A^{-1}$ then calculating $A^{-1}b$ (indeed, it's quicker than either of those steps alone). If you really must invert $A$, just use one of the implementations that already exist in other people's algorithms.
$endgroup$
– user3482749
Jan 11 at 21:33
$begingroup$
In almost all cases, you should just solve $Ax = b$, since that's probably what you want to do anyway, and it's vastly quicker than computing $A^{-1}$ then calculating $A^{-1}b$ (indeed, it's quicker than either of those steps alone). If you really must invert $A$, just use one of the implementations that already exist in other people's algorithms.
$endgroup$
– user3482749
Jan 11 at 21:33
1
1
$begingroup$
See here. The correct, answer, however, is almost certainly "just use somebody else's solution".
$endgroup$
– user3482749
Jan 11 at 22:35
$begingroup$
See here. The correct, answer, however, is almost certainly "just use somebody else's solution".
$endgroup$
– user3482749
Jan 11 at 22:35
1
1
$begingroup$
All six of them are in C.
$endgroup$
– user3482749
Jan 12 at 11:27
$begingroup$
All six of them are in C.
$endgroup$
– user3482749
Jan 12 at 11:27
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
It truly depends on the type of matrix you're going to compute the inverse from. Some methods are better for some classes of matrices than other.
But more importantly, why do you want to invert matrices? In many problems, you don't need to invert matrices, but only need to apply the inverse to some vectors. The latter problem is much easier to tackle, especially from a computational complexity standpoint (e.g. if your matrix is very large) and stability point of view (a matrix could have bad conditioning, be numerically close to non-invertible etc...). Does your application require that compute the matrix inverse?
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
$endgroup$
$begingroup$
No. But I need to find the inverse. Compute it or not.
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:26
add a comment |
Your Answer
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%2f3070297%2fwhat-is-the-best-algorithm-to-find-the-inverse-of-matrix-a%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It truly depends on the type of matrix you're going to compute the inverse from. Some methods are better for some classes of matrices than other.
But more importantly, why do you want to invert matrices? In many problems, you don't need to invert matrices, but only need to apply the inverse to some vectors. The latter problem is much easier to tackle, especially from a computational complexity standpoint (e.g. if your matrix is very large) and stability point of view (a matrix could have bad conditioning, be numerically close to non-invertible etc...). Does your application require that compute the matrix inverse?
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
$endgroup$
$begingroup$
No. But I need to find the inverse. Compute it or not.
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:26
add a comment |
$begingroup$
It truly depends on the type of matrix you're going to compute the inverse from. Some methods are better for some classes of matrices than other.
But more importantly, why do you want to invert matrices? In many problems, you don't need to invert matrices, but only need to apply the inverse to some vectors. The latter problem is much easier to tackle, especially from a computational complexity standpoint (e.g. if your matrix is very large) and stability point of view (a matrix could have bad conditioning, be numerically close to non-invertible etc...). Does your application require that compute the matrix inverse?
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
$endgroup$
$begingroup$
No. But I need to find the inverse. Compute it or not.
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:26
add a comment |
$begingroup$
It truly depends on the type of matrix you're going to compute the inverse from. Some methods are better for some classes of matrices than other.
But more importantly, why do you want to invert matrices? In many problems, you don't need to invert matrices, but only need to apply the inverse to some vectors. The latter problem is much easier to tackle, especially from a computational complexity standpoint (e.g. if your matrix is very large) and stability point of view (a matrix could have bad conditioning, be numerically close to non-invertible etc...). Does your application require that compute the matrix inverse?
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
$endgroup$
It truly depends on the type of matrix you're going to compute the inverse from. Some methods are better for some classes of matrices than other.
But more importantly, why do you want to invert matrices? In many problems, you don't need to invert matrices, but only need to apply the inverse to some vectors. The latter problem is much easier to tackle, especially from a computational complexity standpoint (e.g. if your matrix is very large) and stability point of view (a matrix could have bad conditioning, be numerically close to non-invertible etc...). Does your application require that compute the matrix inverse?
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
answered Jan 11 at 20:14
Stefan LafonStefan Lafon
3,005212
3,005212
$begingroup$
No. But I need to find the inverse. Compute it or not.
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:26
add a comment |
$begingroup$
No. But I need to find the inverse. Compute it or not.
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:26
$begingroup$
No. But I need to find the inverse. Compute it or not.
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:26
$begingroup$
No. But I need to find the inverse. Compute it or not.
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:26
add a comment |
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%2f3070297%2fwhat-is-the-best-algorithm-to-find-the-inverse-of-matrix-a%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
5
$begingroup$
As a non-mathematical comment: for the love of god, don't. Firstly, you probably don't want to invert a matrix at all (see, for example, here). Secondly, use one of the many impementations that already exist.
$endgroup$
– user3482749
Jan 11 at 20:16
$begingroup$
So what should I do?
$endgroup$
– Daniel Mårtensson
Jan 11 at 21:24
$begingroup$
In almost all cases, you should just solve $Ax = b$, since that's probably what you want to do anyway, and it's vastly quicker than computing $A^{-1}$ then calculating $A^{-1}b$ (indeed, it's quicker than either of those steps alone). If you really must invert $A$, just use one of the implementations that already exist in other people's algorithms.
$endgroup$
– user3482749
Jan 11 at 21:33
1
$begingroup$
See here. The correct, answer, however, is almost certainly "just use somebody else's solution".
$endgroup$
– user3482749
Jan 11 at 22:35
1
$begingroup$
All six of them are in C.
$endgroup$
– user3482749
Jan 12 at 11:27