A lower triangular matrix inversion using 2 methods: 1) forward/backward substitution 2)Neumann series

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.

Answer 1

[Gouri Chennuru]

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.