I'm writing an eigensolver and I'm trying to generate a guess for the next iteration in the solve that is orthogonal to to all known eigenvectors calculated thus far. This means that if I have only one eigenvector, that is say 2 million entries long, I need to generate a vector orthogonal to it. I don't think Gram Schmidt works here because I don't have a set of vectors to orthogonalize. What I have is a single vector, in the first eigensolve, and I need to generate another that is orthogonal.

So, in summary: given one vector, create from nothing another vector which is orthogonal to it. The method must support $N$-dimensional vectors (where $N$ could be millions).

I should add that writing a generalized cross product algorithm is not appealing. I'd prefer another way.