Highly ill-conditioned (close to singular) linear problem

[anaemic1]

Hello all,

I have a MATLAB Ax=b problem where A is a matrix generated from the eigenvalues/ vectors of another matrix, which is conditioned well (rcond >eps). A is around 5000 X 5000, complex, has its first half filled with values from the other matrix, and the other half has very few non-zero values (is mostly zeros). It is not suprising that the condition number for A is very high (I was able to reduce rcond to 1e-122 but still it is impossibly huge due to the second half contributing lots of zeros to the diagonal). I've literally tried everything but cannot improve the condition number beyond that. I've also tried 'svd' with tolerance levels but to no avail. There is a check on the validity of my answer, which is - total energy = 100% conserved. Surprisingly, this is true whenever I use linsolve in spite of the unreliable condition number. I suspect this might be due to the higher modes carrying more energy than the lower ones.

Another issue is "OUT OF MEMORY". Although I can recover variables using 'pack' and still complete the program run, I'm sure it will run out of steam after I increase the matrix size to a certain extent. The amazing thing is the program is way faster with linsolve i.e full matrices rather than sparse ones.

I have not used other sparse solvers like Super LU. I would definitely appreciate help from anyone with expertise in these issues or with solvers with capability to tackle ill-conditioned problems. Are there any kind of preconditioner/ scaling codes or do I have to change my system equations/ order?

Thanks and best regards,
Rama

 

[fresh_42]

You could split the matrix into blocks and operate with those blocks. If the matrix has certain "mathematical" properties, then these could be used to simplify the problem. One could also try to write it as a tensor product and use this representation, but trivial algorithms will always go by $O(n^3)$ and $O(n^2)$ is a lower bound.