Parallelization of matrix Gram-Schmidt factorization

General OpenMP discussion

Parallelization of matrix Gram-Schmidt factorization

Postby Giewont » Wed Jan 09, 2013 9:51 am

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

Postby MarkB » Thu Jan 10, 2013 7:25 am

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: 480
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Parallelization of matrix Gram-Schmidt factorization

Postby Oldboy » Thu Jan 10, 2013 8:38 am

Oldboy
 
Posts: 17
Joined: Wed Oct 31, 2012 2:39 am

Re: Parallelization of matrix Gram-Schmidt factorization

Postby Giewont » Fri Jan 11, 2013 11:20 am

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


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 12 guests