1. 300x300 is not a "large" matrix. Large matrices are potentially infinite in the size (like the stiffness matrices in the discretization methods). If you really deal with the sizes like 300x300 (of the matrix, not the discretization grid!), then this is a quite weak motivation for iterative methods: Modern implementations of direct methods could be more efficient.

2. It is not completely clear what you mean under "the determinant exceeds the maximum size". I assume, your matrix is poorly conditioned so that the scaling has no effect. Is this true? Note that then the square ATA (as hinted by Saeed Kazem) could have a worse condition number as A itself.

3. You do not mention, which direct solver you have tried. For ex., is it the Gaussian elimination? With pivoting or without it? Have you tried the Givens rotations or the Householder reflections? If your matrix is poorly conditioned than the latter methods are significantly more stable than the Gaussian elimination (and, surely, than the CG which is a direct method for this matrix size). This is a good choice for problems like those arising in the least squares where difficulties with the almost linearly dependent bases are present.

So, I think, you should look for an appropriate direct solver. For the iterative methods, the situation would be the following: Their efficiency depends not only on the sparcity, but often also on other properties and even the background. For example, if you have no grid hierarchy, geometric multigrid methods are excluded. Simple methods, like Gauss-Seidel, for which the iterations and the setup are computationally cheap, could converge very slowly for poorly conditioned matrices. Method that are currently considered as very efficient (like algebraic multigrid methods) could have a very expensive setup for the 300x300 matrix, but the fast (or any) convergence is not guaranteed. They are all merely constructed for a different application field.

Try Gauss_jordan elimination with full pivoting. See Numerical Recipes in C or in fortran (book online)

Dear Abdallah,

Is there any reason you don't want to try already available highly efficient, parallel solvers, such as LAPACK (direct solvers for dense and banded matrices), HYPER, PETSc etc for general sparse matrices (Krylov type and multigrid) , and even much simpler implementations such as sparsekit2 (BiCGSTAB method in FORTRAN). Most of them provide you with easy methods to populate the matrices or provide function to convert from simple COO format to CSR and other more sophisticate matrix storage formats for general sparsity patterns.

Anyways, if you want to try a basic serial implementation yourself have a look at the Templates for the Solution of Linear Systems which explains how to implement several solvers such as BiCGSTAB, CG, GMRES etc which all consist of level 1 and 2 BLAS operation. Then you can use a sparse implementation of BLAS (and sparse-BLAS) libs to implement you solver. But writing everything from scratch (specially BLAS operations) is probably not be good idea except if you want to explicitly do research on the efficient matrix operation. In that case first few chapters of Matrix operations by Golub which explains the block operations, minimizing cache miss ect, is probably a good starting point.

Hope this helps,

Sina

1. 300x300 is not a "large" matrix. Large matrices are potentially infinite in the size (like the stiffness matrices in the discretization methods). If you really deal with the sizes like 300x300 (of the matrix, not the discretization grid!), then this is a quite weak motivation for iterative methods: Modern implementations of direct methods could be more efficient.

2. It is not completely clear what you mean under "the determinant exceeds the maximum size". I assume, your matrix is poorly conditioned so that the scaling has no effect. Is this true? Note that then the square ATA (as hinted by Saeed Kazem) could have a worse condition number as A itself.

3. You do not mention, which direct solver you have tried. For ex., is it the Gaussian elimination? With pivoting or without it? Have you tried the Givens rotations or the Householder reflections? If your matrix is poorly conditioned than the latter methods are significantly more stable than the Gaussian elimination (and, surely, than the CG which is a direct method for this matrix size). This is a good choice for problems like those arising in the least squares where difficulties with the almost linearly dependent bases are present.

So, I think, you should look for an appropriate direct solver. For the iterative methods, the situation would be the following: Their efficiency depends not only on the sparcity, but often also on other properties and even the background. For example, if you have no grid hierarchy, geometric multigrid methods are excluded. Simple methods, like Gauss-Seidel, for which the iterations and the setup are computationally cheap, could converge very slowly for poorly conditioned matrices. Method that are currently considered as very efficient (like algebraic multigrid methods) could have a very expensive setup for the 300x300 matrix, but the fast (or any) convergence is not guaranteed. They are all merely constructed for a different application field.

300 by 300 is not a very big matrix. Unless it is very badly scaled, simple off-the-shelf methods would work.

If you want to exploit sparsity or special structure then have a look at iterative methods, especially those that are suited for parallel computations. You will find extensive discussion ---both theoretical and step-by-step algorithms--- in:

Parallel Optimization: Theory, algorithms and applications, Oxford University Press, by Censor and Zenios.

See the link below. 

Book Parallel optimization: Theory, algorithms, and applications

I propose yousef sad's book which is in relation of sparse systems.

I agree with the posters before: 300 is not at all a large dimension.

For really large matrices MINRES is a very good canditate in the symmetric case. In the  nonsymmetric situation there is a large number of different iterative solvers available. Using a good preconditioner is typically mandatory to achieve a fast convergence, regardless of the type of method or symmetric / nonsymmetric setting.

The methods for linear systems of equations can be divided into

1. Direct Methods

2. Iterative Methods

DIRECT METHODS

Some of the direct methods discussed are as follows.

1. Gaussian Elimination Method

2. LU-Factorization Method

ITERATIVE METHODS

1. Jacobi Method

2.Gauss-Seidel Method

3.Conjugate gradient Method

4.GMRES Method

Result:

Different direct and iterative methods are discussed to solve linear systems of

equations. It is investigated that GMRES method is the most efficient method to

solve linear systems of equations. It requires less computational time to converge as compared to other direct and iterative methods. Thus, the GMRES method could be considered the more efficient one.

Dear all,

Thank you very much for your helpful answers. Actually, I use the linear algebra software library Armadillo for solving the system by a direct solver. Indeed, I think that the system is ill-conditioned and the scaling has no effect as mentioned by Dmitriy. I noticed that when the system dimension exceeds 125, the determinant becomes inf and the returned solution is wrong. I am looking now to efficient ways in order to handle with this issue.

Thank you,

Cheers

a

Hi Abdallah,

I would suggest using singular value decomposition (e.g. : http://www.cse.unr.edu/~bebis/MathMethods/SVD/lecture.pdf ) or least squares to minimize the error.

Best,

--Hatem

Dear Abdellah,

So try the conjugate gradient (CG) or the biconjugate gradient (BCG) as iterative methods.

Best regards

Dear all,

Thanks a lot for your help. I tried to use the QR decomposition and the results look fine now. Thank you.

Best regards,

a

You may use pre-conditioned GMRES method. We have used Incomplete LU decomposition based pre - conditioner. More details can be seen in our work.

There are few things I would like to highlihgt;

1.you should have posted characteristics of coefficient matrix. It will help to get refined answers.

2. More better you should have posted matrix and some one could have give a try to it.

if you are not yet done with your problem, you can choose to do these things.

Hallo Abdallah Daddi Moussa Ider,

Are you sure that you have a correct formulated problem, because, based on the info you have given, it looks like you have an ill conditioned and spares matrix.

Can you do singular value decomposition on you matrix?

A matrix of 300x300 is relatively small. Direct solvers would be able to solve it without any problem.

Best regards.

300x300 system can be solved using commercial packages like MATLAB/GNU Octave. Form the matrix system in MATLAB and check its condition number say using condest(A) and if it shows very high then your system is ill-conditioned (from your question i get that the determinant of the matrix is large and not infinity so i assume that the matrix is non-singular and the problem is well-posed) and requires preconditioning.

300x300 is not a large matrix dimension! Direct solver MUMPS can easily solve 30 millions x 30 millions linear system. Abdallah Daddi-Moussa-Ider