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.