CODEWITHSUNDEEP
matlablinear-algebra
John
John

Reputation: 3070

How can I choose Gaussian Elimination to solve Ax=b in MATLAB?

I have a question about solving linear equation Ax=b, in which x is unknown, A is square matrix NxN and non-singular matrix.

The vector x can be solved by 

x=inv(A)*b

or

x=A\b

In Matlab, the ‘\’ command invokes an algorithm which depends upon the structure of the matrix A and includes checks (small overhead) on properties of A. Hence, It highly depends on A structure. However, A structure is unknown (i.e random matrix). I want to measure complexity of above equation. Hence, to fairly comparison, I need to fixed the method which I used. In this case, I choose Gaussian Elimination (GE) with complexity O(N^3) My question is how can I choose/fix the method (i.e. GE) to solve above equation?

Upvotes: 1

Views: 889

Answers (1)

Shawn
Shawn

Reputation: 583

One way would be to compute the LU factorisation (assuming A is not symmetric)

[L,U] = lu(A)

where L is a permutation of a lower-triangular matrix with unit diagonal and U is upper triangular. This is equivalent to the Gaussian elimination. Then, when you solve Ax = b, you actually perform first Ly = b and then Ux = y. The important thing is that solving these linear system is essentially O(n^2), while computing the factorisation is O(n^3). So if n is big, you can just measure the time taken to compute the LU factorisation.

For random matrices, you can see the complexity of the LU factorization like that

nn = round(logspace(2, 4, 20)) ;
time = zeros(size(nn)) ;
for i = 1:numel(nn)
    A = rand(nn(i),nn(i)) ;
    tic() ; [L,U] = lu(A) ;
    time(i) = toc() ;
end
loglog(nn,time) ;

(change the "4" to something bigger or smaller, depending on you pc). On my laptop, I have this result

enter image description here

where the slop of 3 (hence, the O(n^3) complexity) is fairly clear.

Upvotes: 2

Related Questions