# Algorithm (parallel and serial) for Gram-Schmidt

Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the subspace perpendicular to $v_1, \dots, v_m$. I could do this by Gram-Schmidt but this would appear to take roughly $(m+n)^3$ time in serial, and cannot be done at all in parallel. Maybe we can assume $m = O(n)$ if this simplifies things.

Are there better algorithms for this? This seems closely related to matrix inversion so one should expect algorithms running in time $n^{\omega}$ (serial) or NC algorithms in time $\log^2 n$ (in parallel). Any references or key words would be greatly appreciated.

• It sounds like you want a QR factorization in $n^\omega$ time. From the matrix pseudoinverse (which I know for sure can be computed in $n^\omega$) you can get a projection matrix for the orthogonal complement of the span of $v_i$. There should be some easy way to get an orthonormal basis from that, but I am not quite seeing it. – Sasho Nikolov Aug 1 '14 at 16:11
• I think Schonhage's paper "Fast Schmidt orthogonalization and unitary transformations of large matrices" from 1973 answers your question. But I can't find it. – Sasho Nikolov Aug 1 '14 at 16:23