# Iterative solution of ill-conditioned matrix systems

I want to solve a matrix system of the form $$Ax=b$$ where $$A$$ is ill-conditioned. The matrix system comes from a structural simulation problem which was discretized using finite elements. I do not have access to the finite element model. I know that proper boundary conditions improve the condition number of the matrix but this should not be the point here.

The matrix system should be solved using an iterative method like CG. What can I do numerically to improve the convergence speed and the accuracy of the solution or even get a useful solution?

• any particular reason why only iterative techniques are considered? Aug 12 '19 at 22:31
• The matrix systems are quite large. They can have billions of unknowns which makes it hard for direct methods to get a solution in a reasonable time. Aug 12 '19 at 22:37
• In this post you can find references to multigrid technique and polynomial precondition. Aug 15 '19 at 14:28
• I already tried multigrid methods but they do not work very well for matrices which arise from FE structural problems and are ill conditioned (condition number about 1e12). The null space seems to play a big role here but I have not yet found an algorithm which shows good results. Aug 16 '19 at 20:28

## 1 Answer

Well if you want a basically guaranteed solution, I'd suggest preconditioned GMRES. If you use flexible GMRES with right preconditioning as well, it can help the condition number of the system while allowing easy evaluation of the convergence. GMRES can stagnate, but it will not diverge, and you can use CG or whatever linear solver you currently have implemented as a preconditioner.

EDIT: CG is also a krylov method that is guaranteed to converge after n steps, so I'd suggest CG with flexible preconditioning.

• Sounds like a good way. Is there also any option to stay at CG with e.g. matrix shifting etc? Aug 12 '19 at 22:06
• I don't think CG has the same benefits as GMRES. You can pretty easily implement BiCGStab (in like a day) and it converges decently and cheaply. and you can precondition it with CG i guess.
– EMP
Aug 12 '19 at 22:19
• This sounds interesting. I have never seen that BiCGStab can be preconditioned with CG. How does it work? Can you provide some literature? Aug 12 '19 at 22:26
• So CG is also a krylov method. So why not just use preconditioned CG?
– EMP
Aug 12 '19 at 23:34
• Well the whole point of preconditioning is to change the condition number of the system you're solving. So maybe your problem is you need a stronger preconditioner. Maybe a line or block solver would work? But I think you need to make sure that your solver doesn't require an SPD preconditioner. IIRC, conjugate residual is similar to CG, but doesn't require that.
– EMP
Aug 13 '19 at 15:29