I am looking for preconditioners which don't assume anything about the matrix or its origins.I basically want to be able to type in the following in MATLAB and have quick solving time:a = rand(5000,5000);b = rand(5000,1);precond_a= my_precond_algorithm(a);qmr(a,b,1e-8,100,precond_a)Needless to say, $a$ is dense.I have looked into:LU works well. But that's no surprise.I am still to find a good algorithm for ILU for dense matrices but I reckon that should work relatively well.Sparse Inverse Approximators (Benzi et. al.) . A paper by Prakash and Mittra discusses the use of Multifrontal Preconds for solving dense Maxwell Equations discretization.Other than LU, I am still a little concerned about the viability of using them as effective preconditioners for large dense matrices. Any resources/comments would be much appreciated!
On Vanilla Preconditioners for solving dense $Ax=b$ iteratively
preconditioning;iterative method
It is critical to know more about the structure. It matters whether the random entries are uniformly or normally distributed and whether there is a shift or not. If there is no structure at all, then you cannot asymptotically beat a direct solve. Some comments on your proposed approachesIncomplete LU is complete LU when applied to a dense matrix. You could consider some thresholding, but it's not likely to work, especially not with a uniform distribution.The inverse is not sparse or have useful decay properties, so a sparse approximate inverse would not be expected to perform well.Integral formulations of Maxwell's equations have very special structure. That paper uses thresholding to create a sparse system. Whether that is beneficial or not (and whether the sparsified matrix is significantly easier to solve with) depends strongly on any special structure in the problem.