Fast calculate the inverse of a lower triangular matrix
19 views (last 30 days)
Show older comments
Hello, Everyone,
I need to write a code on myself to calculate the inverse of a lower triangular matrix. The matrix is a 3000 x 3000 sparse lower triangular matrix.
I found inv.m took 0.015 seconds to finish the calculation, but my code written using Gaussian elimination takes much more time.
Could anyone tell me how to speed up the time of my code?
Thanks.
Benson
1 Comment
Steven Lord
on 16 Jan 2024
I need to write a code on myself to calculate the inverse of a lower triangular matrix.
Do you really need the inverse of the matrix or do you need to solve a system of equations whose coefficient matrix is that lower triangular matrix? In the latter case, don't invert the matrix. Use the backslash operator \ instead.
Could anyone tell me how to speed up the time of my code?
Without seeing your code, it's highly unlikely anyone could give you any concrete suggestions.
Answers (2)
John D'Errico
on 16 Jan 2024
Edited: John D'Errico
on 16 Jan 2024
Do not write your own inverse code. Gaussian elimination is great for teaching a student about matrices, but too often they then think they know it all. (This can extend to the doctoral level and beyond.) You don't. And you certainly do not want to write it in MATLAB on a sparse matrix.
Is inv too slow? Well, big problems take time. Your computer is not infinitely fast or infinitely powerful. Not even close.
Most important is to understand why you think you need to compute that inverse! Almost always, you don't. If 0.015 seconds is too slow, then you are doing it a zllion times. So what are you doing with that inverse? Are you multiyplying another matrix with it? WRONG!!!!!!
Use backslash instead. For example...
A = sparse(triu(tril(rand(3000)),-2));
So A is sparse lower triangular. Compare these times...
V = rand(3000,1);
timeit(@() inv(A)*V)
timeit(@() A\V)
DON'T COMPUTE AN INVERSE. You very rarely need to compute an inverse, even if a formula has the inverse written. That inverse is just a nice mathematical way of writing what you need to do, in MATLAB, usually performed best using backslash. If you are post multiplying by the inverse, then forward slash would apply. If you want better help than this, then you need to show exactly what you are doing with that inverse.
Far too often people think just because a formula shows an inverse, that they need to compute that inverse.
11 Comments
Steven Lord
on 17 Jan 2024
My question is why Matlab code (inv.m) is so fast, especially in the linear sparse equation solving?
Because we've put in a lot of effort over the decades at making the linear algebra functionality in MATLAB fast and good. [In the project management triangle I'd argue we've chosen "good" and "fast". The amount of design, implementation, and testing work we've done and continue to do pretty much rules out "cheap".]
Since you wrote:
I actually want to implement inv.m in C++ for a lower triangular sparse matrix.
you may be able to generate code using MATLAB Coder for this (the inv documentation page does list "C/C++ Code Generation" as an extended capability for this function and MATLAB Coder does have a documentation page for sparse matrix code generation support).
Matt J
on 17 Jan 2024
Edited: Matt J
on 17 Jan 2024
My question is why Matlab code (inv.m) is so fast, especially in the linear sparse equation solving?
Again, because it knows and exploits the fact that L is triangular, not just that it is sparse. You haven't confirmed whether your 3rd party code does that.
you may be able to generate code using MATLAB Coder for this (the inv documentation page does list "C/C++ Code Generation" as an extended capability
And for that matter, linsolve is supported by Matlab Coder as well. This would allow you to stipulate directly that the matrix is lower triangular,
opts.LT=true; %notifies linsolve that L will be lower triangular
inverseL=linsolve(L, speye(size(L)),opts);
Matt J
on 16 Jan 2024
Edited: Matt J
on 16 Jan 2024
Do you really need the inverse of the matrix or do you need to solve a system of equations whose coefficient matrix is that lower triangular matrix? In the latter case, don't invert the matrix. Use the backslash operator \ instead.
Or, perhaps linsolve? This allows you to inform the solver that the matrix is lower triangular.
opts.LT=true;
x=linsolve(A,b,opts);
0 Comments
See Also
Categories
Find more on Sparse Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!