5
$\begingroup$

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:

  1. LU works well. But that's no surprise.

  2. I am still to find a good algorithm for ILU for dense matrices but I reckon that should work relatively well.

  3. Sparse Inverse Approximators (Benzi et. al.) .

  4. 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!

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you mean a quick solving time including computing the preconditioner? Or just the speed at which QMR converges on the result of a given input vector? $\endgroup$ – meawoppl Mar 1 '12 at 23:35
  • $\begingroup$ @meawoppl, I want to ideally, generate the preconditioner (parallel-ly) and reduce the number of iterations for QMR to converge to 1e-8 residual. (Which is same as saying that I want to speed up the execution time of QMR). But then, I don't want to spend a too much time generating a good preconditioner. I am looking for an overall reduction in time of execution. $\endgroup$ – Inquest Mar 2 '12 at 14:32
  • $\begingroup$ Are you specifically interested in random matrices are you just trying to precondition general dense matrices? If the latter, I am afraid you are out of luck. Preconditioning in general will require some knowledge about the structure or purpose of your matrix. $\endgroup$ – Andrew T. Barker Mar 5 '12 at 19:14
  • $\begingroup$ I'm trying to precondition general dense matrices. (The latter). Usuallly, preconditioner design does require structure or purpose but thats the point! I'm looking for a preconditioner which doesn't need this information. It should be completely vanilla. $\endgroup$ – Inquest Mar 6 '12 at 9:57
  • $\begingroup$ Are the entries of the matrix real, complex, or something else? $\endgroup$ – Dan Mar 7 '12 at 19:07
10
+50
$\begingroup$

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 approaches

  1. Incomplete 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.

  2. The inverse is not sparse or have useful decay properties, so a sparse approximate inverse would not be expected to perform well.

  3. 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Although I'm sure that there is no structure, I am also fairly certain that there is no uniform distribution. Does thresholding look good then? I have attempted it (crudely:: using a very primitive scheme of $A(i,j) = 0$ if $A(i,j) < \alpha \max(\max(A(i,:)),\max(A(:,j)))$ but sadly, it didn't help speed up the convergence. (Of course, there is overhead associated with the maximum and minimum calculation but still.....) Can you point me to some literature regarding this? $\endgroup$ – Inquest Mar 8 '12 at 7:49
  • $\begingroup$ What prior knowledge do you have about the matrix or the physical process it represents? If you have no prior knowledge, then just use LU. If you have some prior knowledge, that should be the first thing you disclose in the problem statement. What process does this matrix represent? $\endgroup$ – Jed Brown Mar 8 '12 at 14:31
  • $\begingroup$ Nothing. For all I know, it could be a set of random numbers. What I am trying to do is find an A\b for the Krylov world, this is impossible without a strong preconditioner. Using LU (without thresholding) is no different from A\b but maybe thresholding will help? $\endgroup$ – Inquest Mar 8 '12 at 15:12
  • $\begingroup$ You are wasting your time. Every mystery ever solved has turned out to be ... not magic. --Tim Minchin ("Storm") $\endgroup$ – Jed Brown Mar 8 '12 at 16:49
  • 4
    $\begingroup$ Use a direct solve. You are looking for a shortcut that does not exist. If you want something faster, you have to use the structure provided by the problem. Real problems have some structure, even if it is just statistical. Some kinds of structure is harder to use than other kinds. Matrices are linear transformations. What is the meaning of the spaces your matrix maps between and what process does it represent? You are wasting your time (looking for magic) if you don't answer this question first. $\endgroup$ – Jed Brown Mar 8 '12 at 18:15
6
$\begingroup$

I think if there were a preconditioner which

  • was general in the sense of working for an arbitrary dense matrix without defined structure or contents
  • accelerated your solution rate without other drawback

then you would always use it in your solution algorithim, and thus it would become part of your solver.

Improve this answer
$\endgroup$
5
$\begingroup$

For dense matrices without structure, polynomial preconditioning is probably the only viable method, though it has limitations (see, e.g., http://amath.colorado.edu/pub/iterative/psi-phi.ps.Z). If your matrix has entries of different magnitudes, it may be necessary that you first scale your matrix using a matching http://www.cerfacs.fr/algor/reports/1997/TR_PA_97_45.ps.gz

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.