5
$\begingroup$

I've heard that classical Gram-Schmidt is more amenable to parallelization than modified Gram-Schmidt; apparently the reason has something to do with "level 2 BLAS", which I'm not familiar with. Also, in a comment on this question, @Jed Brown talks about left-looking and right-looking Gram-Schmidt, which I haven't found a reference to.

How is the Gram-Schmidt algorithm parallelized in practice, and how effective is the parallelization?

$\endgroup$
1
$\begingroup$

First, Blas(Basic Linear Algebra Subprograms) is a collection of highly optimized low level functions performing standard linear algebra operations such as scaling, dot product and matrix multiplication. Therefore it is desirable to make use of these functions for optimal performance.

The major advantage of the modified Gram-Schmidt(MGS) over the classic Gram-Schmidt is that it offers better stability by rearranging the order of operations. Threfore it is often used in practice. Unfortunately, the MGS cannot be expressed by BLAS routines and requires additional communication when implemented in parallel.

In practice you will resort to some parallel programming language such as OpenMP or CUDA, if you own a graphics card. In the article http://www.drdobbs.com/go-parallel/article/print?articleId=240006334&siteSectionName= they mention a speed up of a factor 3 over serial implementation using OpenMP and almost a factor 9 when using OpenACC with a problem size of $10^3 \times 10^3$. You may also take a look at http://link.springer.com/article/10.1140/epjst/e2012-01638-7#page-1 for a comparison between GPU and CPU implementations.

$\endgroup$
  • 1
    $\begingroup$ No - Matrix multiplication is level-3, and dot products are level-1. The idea is: vector-vector operations, with cost $O(n)$, are level-1; matrix-vector operations, with cost $O(n^2)$, are level-2; matrix-matrix operations, with cost $O(n^3)$, are level 3. See en.wikipedia.org/wiki/…. $\endgroup$ – Federico Poloni Sep 2 '14 at 11:43
  • $\begingroup$ YOU are right. Thank you for pointing out the exact nomenclature of the BLAS package. I updated my post. $\endgroup$ – nico Sep 2 '14 at 13:50

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.