# Parallel Gram-Schmidt algorithms

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?

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.
• 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/…. – Federico Poloni Sep 2 '14 at 11:43