## Parallelization of matrix Gram-Schmidt factorization

General OpenMP discussion

### Parallelization of matrix Gram-Schmidt factorization

Hello !

I try parallelize this code (the Gram-Schimdt QR factorization algorithm):
Code: Select all
`int i, j, k;double r[50][50], q[50][50], a[50][50];#pragma omp parallel for private (k, i, j) shared (r, a, q)for (k=0; k<50; k++){      r[k][k]=0;      for (i=0; i<50; i++)      {        r[k][k] = r[k][k] + a[i][k] * a[i][k];      }      r[k][k] = sqrt(r[k][k]);            for (i=0; i<50; i++)      {          q[i][k] = a[i][k]/r[k][k];      }           for(j=k+1; j<50; j++)      {        r[k][j]=0;        for(i=0; i<50; i++)  r[k][j] += q[i][k] * a[i][j];        for (i=0; i<50; i++) a[i][j] = a[i][j] - r[k][j]*q[i][k];      }}`

but it doesn't work correctly...
it produces bad, meaningless results, completely different than non-paraller version.

I observed that a problematic fragment is:
Code: Select all
`    for (i=0; i<3; i++)          {              q[i][k] = a[i][k]/r[k][k];          }`

but I don't know why it's working wrong.

Anybody help / tell me how can I implement the algorihtm as a paraller, good working version ?
Giewont

Posts: 2
Joined: Mon Jan 07, 2013 9:46 am

### Re: Parallelization of matrix Gram-Schmidt factorization

Hi there,

The k loop is not parallelisable in this algorithm: the values of r depend on those computed in the previous k iteration.
You can parallelise the loops at the next level down: however the efficiency will be poor for small matrices.
You would be most likely better off using a library routine to do this (from Intel MKL for example, which supports OpenMP).

Hope that helps,
Mark.
MarkB

Posts: 577
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Parallelization of matrix Gram-Schmidt factorization

Oldboy

Posts: 18
Joined: Wed Oct 31, 2012 2:39 am

### Re: Parallelization of matrix Gram-Schmidt factorization

MarkB & Oldboy - Thank You for your posts, but I must use this algorithm which I presented (it's impose by my college...).

In this case, do you have any idea of rewriting this algorithm to equivalent form, which can be parallelize ??
I don't know how I can do this and till now anybody can't help me :/
Giewont

Posts: 2
Joined: Mon Jan 07, 2013 9:46 am