[Solved]: Does PETSc really give speedup?

Problem Detail: 

I searched linear solver library and found out PETSc library which considered to be powerful and useful library. PETSc consists implementations of various iterative methods with preconditioners and sparse matrix storing methods. All methods are realized sequentially and in parallel using MPI.

I was very glad for creaters of PETSc. I downloaded it and installed. However, when I start reading user's guide I encountered following text:

PETSc should not be used to attempt to provide a "parallel linear solver" in an otherwise sequential code. Certainly all parts of a previously sequential code need not be parallelized but the matrix generation portion must be parallelized to expect any kind of reasonable performance. Do not expect to generate your matrix sequentially and then "use PETSc" to solve the linear system in parallel. 

I was surprised! Did PETSc developers really parallelize only matrix generating part? What is a benefit of using PETSc as parallel solver if linear system solving part runs sequentially?

Asked By : Nurlan

Answered By : Wandering Logic

You misread the text. The authors of PETSc are just telling you that you can't avoid Amdahl's law.

They have done their best to parallelize every aspect of the linear solver. But a real program is not just a call to a linear solver. First you generate a matrix and then you pass the matrix to the linear solver. If your matrix generator is slow, your whole program will be slow.

For example, suppose your original program spends 1000 seconds generating the matrix $A$ and vector $b$ and then you call a linear solver. Your old (sequential) linear solver took 1000 seconds to find $x$ such that $Ax = b$. Now you replace your old sequential linear solver with PETSc. Suppose the PETSc authors did such a good job that the PETSc parallel linear solver finds $x$ in just 1 second! Now how long does it take your program to run? 1001 seconds. You got less than 2x speedup! You need to do some work on your matrix generation code if you want to get a better speedup.

Pretty much the authors of PETSc are just telling you that a parallelized linear solver library is not a magic bean.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12670