2
$\begingroup$

I am using the ScaLAPACK PDGESV routine to solve large dense linear systems distributed over many supercomputer nodes, but ultimately I only need a small portion of the solution vector (e.g. the first 10 out of 500,000 elements), and I'm wondering if there is a way to take advantage of the fact that I don't need the entire solution to speed up the calculation. PDGESV comes with a lot of MPI overhead and I'm hoping some communication can be avoided.

$\endgroup$

1 Answer 1

3
$\begingroup$

The only way that I'm aware of to take advantage of only needing a partial solution is in the triangular solves. But those are usually a small part of the total time in dense LU (unless you have many right-hand sides).

You might be able to use a non-pivoted LU, to avoid the cost of pivoting. However, the solution might not be accurate and may require some form of iterative refinement. Also, ScaLAPACK doesn't have a non-pivoted LU, so you'd need something like SLATE (which has a ScaLAPACK-compatibility API). (I think there are some other non-pivoted options. But, I'm part of the SLATE team, so that's the one I'm familiar with.)

If non-pivoted LU is giving better performance but not the necessary stability, there are a few techniques that can help improve stability. This is an area of my research, so I'd be happy to go into more detail if you're interested.

Relatedly, if your supercomputer has GPUs, I'd strongly encourage you to use SLATE instead of ScaLAPACK. GPUs have much better performance and may reduce the number of nodes you need.

$\endgroup$
10
  • 2
    $\begingroup$ One application where the triangular solves take a significant amount of time is in implementations of the simplex method for LP. There are specialized routines for doing the triangular solve that take advantage of sparsity in the right hand side vector and solution. $\endgroup$ Commented Apr 14, 2023 at 14:20
  • 3
    $\begingroup$ @BrianBorchers Yea, that's definitely a case with many right hand sides. I assumed OP was doing something different because I didn't think there were dense LP problems with 500,000 constraints. But I'm happy to be corrected (especially if the performance of partial pivoting is lacking). $\endgroup$ Commented Apr 14, 2023 at 22:49
  • 1
    $\begingroup$ If you are involved with SLATE professionally please disclose it in your post together with your recommendation; these are the rules on SE. $\endgroup$ Commented Apr 15, 2023 at 9:05
  • 1
    $\begingroup$ (That said, I do not want to discourage you: thanks for answering and sharing your expertise on this topic; I have upvoted you!) $\endgroup$ Commented Apr 15, 2023 at 10:59
  • 1
    $\begingroup$ @FedericoPoloni That's a good rule. Thanks for bringing it to my attention. $\endgroup$ Commented Apr 15, 2023 at 13:40

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.