Board index » cppbuilder » Re: Matrix Operation

Re: Matrix Operation


2005-04-20 12:29:00 AM
cppbuilder76
"Mohsen" < XXXX@XXXXX.COM >writes:
Quote
Matrix multiplication using loops, when the dimensions are
considerably large takes a long time. Is it possible to replace
the loops that use indexes in order to access elements of matrix
with loops that increment pointers to elements and speed things
up?
Whether it is possible depends on how the matrix elements are stored.
Whether it speeds things up has to be measured.
 
 

Re:Re: Matrix Operation

Mohsen wrote:
Quote
Matrix multiplication using loops, when the dimensions are
considerably large takes a long time. Is it possible to replace
the loops that use indexes in order to access elements of matrix
with loops that increment pointers to elements and speed things
up?
Yes.
Quote
Is there any efficient way to do so (a better one than using
pointers)?
Not better, but in addition to it....
Small loops are very inefficient because the CPU must flush and refill
it's execution pipeline so often. You will see speed improvments if
you calculate 2, 4, 8 or even 16 cells per loop.
for( x=0; x<32; ++x )
{ for( y=0; y<32; y+=n)
{
inline_calc using x, y
inline_calc using x, y+1
. . . .
inline_calc using x, y+n-1
} }
 

Re:Re: Matrix Operation

Hi,
Matrix multiplication using loops, when the dimensions are
considerably large takes a long time. Is it possible to replace
the loops that use indexes in order to access elements of matrix
with loops that increment pointers to elements and speed things
up? Is there any efficient way to do so (a better one than using
pointers)?
Thnx
Mohsen
 

{smallsort}

Re:Re: Matrix Operation

Quote

Whether it is possible depends on how the matrix elements are stored.
How can I store a two dimension matrix efficiently? Is there a
better alternate for the following?
double** data;
data = new double* [rows];
for (unsigned i = 0; i < rows; i++)
data[i] = new double[columns];
Quote

Whether it speeds things up has to be measured.
 

Re:Re: Matrix Operation

Quote
How can I store a two dimension matrix efficiently? Is there a
better alternate for the following?

double** data;

data = new double* [rows];

for (unsigned i = 0; i < rows; i++)
data[i] = new double[columns];

One example is the sparse matrix (one with lots of zero elements).
www.nist.gov/dads/HTML/sparsematrix.html
Boost has an implementation:
www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm
 

Re:Re: Matrix Operation

"Mohsen" < XXXX@XXXXX.COM >writes:
Quote
>Whether it is possible depends on how the matrix elements are stored.

How can I store a two dimension matrix efficiently? Is there a
better alternate for the following?

double** data;

data = new double* [rows];

for (unsigned i = 0; i < rows; i++)
data[i] = new double[columns];
There are many ways to store a matrix, and you didn't tell us which
one you are using, so I asked.
What is better depends on your requirements. Among those I usually
want to meet are simplicity of the code and robustness. Therefore, I'd
wrap these arrays up in smart pointers or container objects.
One obvious alternative is an array with rows*columns elements. This
will certainly speed up both allocation and deallocation. I'm not an
expert, but the contiguity of all the elements also might have an
impact on how the matrix can be cached.
 

Re:Re: Matrix Operation

XXXX@XXXXX.COM (Thomas Maeder [TeamB]) writes:
Quote
One obvious alternative is an array with rows*columns elements. This
will certainly speed up both allocation and deallocation. I'm not an
expert, but the contiguity of all the elements also might have an
impact on how the matrix can be cached.
Oh, and you'll also dereference one less pointer per element access.
 

Re:Re: Matrix Operation

Quote
One example is the sparse matrix (one with lots of zero elements).
www.nist.gov/dads/HTML/sparsematrix.html

Boost has an implementation:
www.boost.org/libs/numeric/ublas/doc/matrix_sparse.htm

--
Bruce


Do you work on sparse matrix technology?
 

Re:Re: Matrix Operation

XXXX@XXXXX.COM (Thomas Maeder [TeamB]) wrote:
Quote
XXXX@XXXXX.COM (Thomas Maeder [TeamB]) writes:

>One obvious alternative is an array with rows*columns elements. This
>will certainly speed up both allocation and deallocation. I'm not an
>expert, but the contiguity of all the elements also might have an
>impact on how the matrix can be cached.

Oh, and you'll also dereference one less pointer per element access.
But this has the drawback that in order to access the elements
of farthest rows great number of multiplication is necessary.
I've wrapped the matrix in a template. I've noticed that the
compiler generates a code such as this one
mov esi, [esi+ebx*4]
for an indexed access to individual elements of an array such
as this one:
for (unsigned i = 0; i < n; i++)
a = array[i] * 2;
but this one produces a better code:
double* ptr1 = array;
double* ptr2 = ptr1 + n;
for (; ptr1 < ptr2; ptr1++)
a = *ptr1 * 2;
This eliminates the multiplication by 4 in previous assembly
code and could have a great influence when the dimensions are
large. But in matrix case it is inevitable to bypass the
problem mentioned above and I thought it could be solved by
changing the way we save the matrix. For example accessing the
elements in each row is OK, but elements in columns still have
the same problem. I don't know whether I could clarify my
problem.
Mohsen
 

Re:Re: Matrix Operation

"Mohsen" < XXXX@XXXXX.COM >writes:
Quote
But this has the drawback that in order to access the elements
of farthest rows great number of multiplication is necessary.
Oh yes, there are benefits and drawbacks in every you store a
matrix. The optimal layout will depend on the way the matrix is most
often used.