Is there an iterative solver for dense matrices with possible zero diagonal entries?

Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $$10^{th}$$-order) and my matrix is a "Vandermonde-like" system that results in zeros for the odd-powered polynomial basis functions when my sample space is symmetric with respect to the vertical axis of the local reference frame in which I'm fitting the polynomial. I have tried Gauss-Seidel and LUSGS, but later realised that they both rely on non-zero diagonal entries.

Edit: I have double-checked that the system is correctly implemented because it solves with Gauss elimination with back-substitution (LUP decomposition). However, this is too slow for my application (the $$10^{th}$$-order matrix is $$121\!\times\! 121$$), and would prefer an iterative solver.

• What makes you think that an iterative solver will be faster than LUP for a small dense (and probably poorly conditioned) matrix like this? Jul 1 '20 at 13:58
• If the eigenvalues of the matrix are clustered, there is no reason to believe that an iterative solver might not be faster. For example, if there were only 10 distinct eigenvalues, then most iterative solvers will converge in 10 iterations requiring $10n^2$ operations -- still faster than the $O(n^3)$ for an LU decomposition. Jul 1 '20 at 17:32
• @WolfgangBangerth there's no particular reason to believe that eigenvalues will be clustered. Jul 1 '20 at 18:46
• @wolfgang bangerth, thinking in terms of complexities won't accurately depict behaviour for such small matrices. A simple LU will probably be orders of magnitude faster here. Especially if using a library like LAPACK. Jul 1 '20 at 18:47
• @ThijsSteel -- ah, I had not realized the matrix is small. You're likely right that for a 121x121 matrix, LU decomposition is likely faster than anything else, unless you only care about very relaxed accuracy. Jul 2 '20 at 1:31

What you probably had in mind is the question of preconditioning, and that you can't use things such as Gauss-Seidel or Jacobi preconditioning. That is true, but depending on what else you know of the matrix, you can do something like a "block" version of Jacobi (or Gauss-Seidel, or SSOR, or ...) in which you consider $$2\times 2$$ blocks of the matrix which might be invertible.
• Okay, thank you for your response! I will implement GMRES and compare speeds. The reason I mentioned that Gauss-Seidel didn't work is because I implemented the algorithm on Wikipedia, which requires division by diagonal entries $A_{ii}$. Jul 1 '20 at 14:20