A lower triangular matrix inversion using 2 methods: 1) forward/backward substitution 2)Neumann series
14 views (last 30 days)
Show older comments
Nurulhuda Ismail
on 9 Mar 2020
Answered: Gouri Chennuru
on 12 Mar 2020
Hi,
I tried to solve a linear equation using Gauss-Seidel method and execute it in MATLAB. To solve a lower triangular matrix inversion in the Gauss-Seidel method, I use 2 different approaches: 1) Forward/Backward substitution method, 2) Series of matrix multiplication or we called it Neumann series.
1) Forward Substitution method
invL=zeros(K,K);
nn=length(L);
I=eye(K);
for k = 1:nn
for i = 1:nn
invL(k,i) = (I(k,i) - L(k,1:(k-1))*invL(1:(k-1),i))/L(k,k); % Lower triangular matrix inversion (L^(-1))
end
end
2) Neumann series
LL= 1:1:4
Ik=eye(K);
theta=1/D; %D is a diagonal matrix which consists of a diagonal elements of a lower triangular matrix L
t=(Ik-(theta*L)); %inner loop of Neumann series technique
T=zeros(K,K);
for n=0:LL
t1=t^n;
T=T+t1;
end
InvL=T*theta; %Lower triangular matrix inversion (L^(-1))
Based on the results, I found that the execution time using Neumann series is shorter than Forward/backward substitution, even though the computational complexity of Forward/backward substitution is simpler than the Neumann series. Why this happen?
Hope to hear from you.
Thank you.
0 Comments
Accepted Answer
Gouri Chennuru
on 12 Mar 2020
In case of Forward Substitution Method,
The time complexity is O(n^2) because there is nested for loop and the statement,
invL(k,i) = (I(k,i) - L(k,1:(k-1))*invL(1:(k-1),i))/L(k,k);
gets executed for nn^2 times.
In case of Neumann series,
The time complexity is O(n) because the set of statements inside the for loop i.e.,
t1=t^n;
T=T+t1;
Get executed for LL times.
0 Comments
More Answers (0)
See Also
Categories
Find more on Loops and Conditional Statements 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!