Azzera filtri
Azzera filtri

Fast calculate the inverse of a lower triangular matrix

65 visualizzazioni (ultimi 30 giorni)
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 Commento
Steven Lord
Steven Lord il 16 Gen 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.

Accedi per commentare.

Risposte (2)

John D'Errico
John D'Errico il 16 Gen 2024
Modificato: John D'Errico il 16 Gen 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)
ans = 0.2030
timeit(@() A\V)
ans = 3.5245e-05
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 Commenti
Steven Lord
Steven Lord il 17 Gen 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
Matt J il 17 Gen 2024
Modificato: Matt J il 17 Gen 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);

Accedi per commentare.


Matt J
Matt J il 16 Gen 2024
Modificato: Matt J il 16 Gen 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);

Categorie

Scopri di più su Sparse Matrices in Help Center e File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by