-3
$\begingroup$

I have a question about direct and iterative method. Many people including me often say that for very large sparse linear system, Ax=b, an iterative method is necessary because of cpu memory. I also believe that ideas.

But, recent days, I find that MATLAB direct methods command A\b for large sparse system is also fast. So, in my opinion, if an author proposes a new iteration method, he/she must compare the cpu time between the new method and MATLAB A\b. If his method is faster than A\b, then I trust that his new iteration method is better and successful. Otherwise, I can't trust that a new iteration method is a successful one if one method can't beat MATLAB A\b. Actually, in most papers, most people do not compare the CPU time in their numerical examples with A\b. So I still have doubts about their so-called a better method.

So, whether we should compare our new iteration method with matlab A\b the cpu time? Because I think if one can beat matlab function, then it will be more persuasive, right? if not, then we will prefer to matlab built-in function,right? thanks.

$\endgroup$
5
  • 1
    $\begingroup$ I believe MATLAB's solver is based on Tim Davis's SUITESPARSE (see faculty.cse.tamu.edu/davis/suitesparse.html). Direct methods are suitable for smaller problems which you can fit in memory. For large A's you will have to use preconditioned iterative methods. $\endgroup$
    – stali
    Oct 23 '19 at 9:49
  • $\begingroup$ @stali thanks for reply, yes, we often say that direct methods are suitable for smaller matrix size, but if one does not list the cpu time between his new method and A\b in his numerical examples, how do I believe that his method is better than A\b? I find in many papers, the author's matrix size of his examples is not large enough to persuade me to believe the old saying that "for large matrix, iterative methods are necessary ". I think if one want to insist his new method is better than A\b, he must give a large matrix that A\b fails, but his new iterative method can do. $\endgroup$
    – sunshine
    Oct 23 '19 at 11:06
  • $\begingroup$ I think comparing the actual runtime is only part of the argument. CPU architecture and performance change all the time, so the better and depper comparison lies in the algorithm. If you think your method is better, I would focus on explaining or investigatinge the reason for that. If you clearly explain why you expect method x to be faster than y, then that is worth more than pushing a matlab button. $\endgroup$
    – MPIchael
    Oct 23 '19 at 11:56
  • 1
    $\begingroup$ These topics have been discussed numerous times. It really depends how the solver scales (FLOPS & Memory wise) with the size of A. Please see similar threads, e.g., scicomp.stackexchange.com/questions/7997/… $\endgroup$
    – stali
    Oct 23 '19 at 12:20
  • $\begingroup$ Also, Matlab is not used for HPC, so I'm not going to compare to matlab's A\b because I'm writing in Fortran. Furthermore, the nice thing about A\b is that it choose good methods no matter what you give it. It's general. But when I write my code, I know significantly more about my matrix than matlab, so I can choose the best case, saving me time and coding hassle. $\endgroup$
    – EMP
    Oct 23 '19 at 15:15
3
$\begingroup$

It's almost impossible to say whether a direct solver will outperform an iterative solver or vice-versa without knowing more specific information about the sparse matrix. The key problem with direct solvers is fill-in, which happens during factorization phase and causes a lot of extra memory consumption. But not all sparse matrices will have a devastating fill-in when used with a direct solver. For example, tridiagonal matrices can often be solved with very little extra intermediate memory and so assuming that pivoting isn't necessary for stability it's fairly routine to solve a tridiagonal system even with billions of rows on today's workstations.

On the other hand if the matrix is coming from a 3D partial differential equation, then you'll be very lucky to fit the factorization of a system containing more than 10-million rows on a typical workstation of today (having say 128 GB of RAM), even with best-in-class fill reduction orderings done beforehand.

So the size of a system is often used as a guideline for when to switch over to iterative, but really the problem is the system's structure and how that contributes to fill-in during factorization. If that structure results in significant fill-in, then it is necessary to switch to iterative methods. But iterative methods never completely remove the dependency on direct methods, as they will need preconditioners and the building block of preconditioners are almost always direct solvers.

In the last decade or so there has been research on compression techniques to deal with the fill-in problem, particularly on those systems which lend themselves to very bad fill-in. I don't think these techniques have found their way into mainstream direct solvers yet, but when they do it might change the way people think about when it is necessary to switch to iterative solvers.

$\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.