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

I was very glad for the creators of PETSc. I downloaded and then installed it. However, when I started reading user's guide I encountered the 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 the matrix generating part? What is a benefit of using PETSc as a parallel solver if the linear system solving part runs sequentially?


1 Answer 1


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.

  • $\begingroup$ you mean major benefit from using PETSc is got from generating parallel matrix rather than solving it? Suppose I will count execution time only for solving linear system, in this case ex. time will not depend whether matrix generated sequentially or in parallel. What is speedup of matrix solving part excluding matrix generating? $\endgroup$
    – Nurlan
    Jun 17, 2013 at 11:05
  • 2
    $\begingroup$ No. The major benefit from using PETSc is going to come from using the Krylov solvers on huge matrices. The documentation says that you need about 20000 unknowns per parallel process. Once you reach that point and you are on a machine with low cost communication for MPI you should get nearly linear speedups. So with a system with 1 million unknowns, I'd expect you'd get approximately linear speedups for the solver on a server with 32 cores (4 Xeons or 4 Opterons). $\endgroup$ Jun 17, 2013 at 13:42
  • 2
    $\begingroup$ (As compared to solving the same system on a single core of the same server.) The point is: PETSc can speed up only the linear solver. Everything else is your problem. $\endgroup$ Jun 17, 2013 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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