### Gram-Schmidt matrix factorization

Hello !

I'm very beginner in numerical methods... I have the pseudo-code
(look at image), but I don't know how intrepret this and how
I can implement this in C++...

Can You help me ?

image of pseudo-code:
http://postimage.org/image/o6sitd3l9/
Factorization? Gram-Schmidt is for orthonormalizing a basis. Start with a (numbered) set of vectors. Take the first one, normalize it (divide it by it's length) then fix the remaining ones so that their scalar product with the first one is 0 (using the last formula in the picture). Repeat for the remaining vectors.

If unclear, the algorithm should be well explained in wikipedia.
I looked for a numerical example of the method.

I wrote the C program and I have verified that the results correspond to those of the example.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546`` ``````#include #include #include using namespace std; // example: http://www.mia.uni-saarland.de/Teaching/NAVC-SS11/sol_c8.pdf // page 5 double a[3][3] = { {1.0, 2.0, 1.0}, {0.0, 1.0, 2.0}, {1.0, 2.0, 0.0} }; // any column of a is a vector double r[3][3], q[3][3]; int main(int argc, char *argv[]) { int k, i, j; for (k=0; k<3; k++){ r[k][k]=0; // equivalent to sum = 0 for (i=0; i<3; i++) r[k][k] = r[k][k] + a[i][k] * a[i][k]; // rkk = sqr(a0k) + sqr(a1k) + sqr(a2k) r[k][k] = sqrt(r[k][k]); // ||a|| cout << endl << "R"<
Last edited on
 I wrote the C program and I have verified that the results correspond to those of the example.

Thank You very much ! It works really good :)

I have one more, additional question: do You know (or somebody...) how can I convert it to parallel version using OpenMP ?

I tried to use:

 ``123`` ``````int k, i, j; #pragma omp parallel for private (k, i, j) shared (a, q, r) // ........ ``````

but it doesn't work correctly. I noticed that the problematic fragment is:

 ``123`` ``````for (i=0; i<3; i++) { q[i][k] = a[i][k]/r[k][k]; }``````

but I don't know why it makes a problem...

How would you parallelize this? It's a pretty sequential algorithm. I guess if you have a ridiculous number of dimensions, it might be doable...
It's an exercise for my college. I must parallelize the sequential Gram-Schmidt's algorithm and compare execution time of both version (of course for large matrix).

Topic archived. No new replies allowed.