Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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.
