Make efficient - A symmetric matrix multiplication

Question

As per following the inital thread make efficient the copy of symmetric matrix in c-sharp from cMinor.

I would be quite interesting with some inputs in how to build a symmetric square matrix multiplication with one line vector and one column vector by using an array implementation of the matrix, instead of the classical

long s = 0;
List<double> columnVector = new List<double>(N); 
List<double> lineVector = new List<double>(N); 
//- init. vectors and symmetric square matrix m

for (int i=0; i < N; i++)
{
    for(int j=0; j < N; j++){
        s += lineVector[i] * columnVector[j] * m[i,j];
    }
}

Thanks for your input !

Answer 1

You could make matrix multiplication pretty fast with unsafe code. I have blogged about it.

Answer 2

The line vector times symmetric matrix equals to the transpose of the matrix times the column vector. So only the column vector case needs to be considered.

Originally the i-th element of y=A*x is defined as

y[i] = SUM( A[i,j]*x[j], j=0..N-1 )

but since A is symmetric, the sum be split into sums, one below the diagonal and the other above

y[i] = SUM( A[i,j]*x[j], j=0..i-1) + SUM( A[i,j]*x[j], j=i..N-1 )

From the other posting the matrix index is

A[i,j] = A[i*N-i*(i+1)/2+j]  // j>=i
A[i,j] = A[j*N-j*(j+1)/2+i]  // j< i

For a N×N symmetric matrix A = new double[N*(N+1)/2];

In C# code the above is:

int k;
for(int i=0; i<N; i++)
{
    // start sum with zero
    y[i]=0;
    // below diagonal
    k=i;
    for(int j=0; j<=i-1; j++)
    {                    
        y[i]+=A[k]*x[j];
        k+=N-j-1;
    }
    // above diagonal
    k=i*N-i*(i+1)/2+i;
    for(int j=i; j<=N-1; j++)
    {
        y[i]+=A[k]*x[j];
        k++;
    }
}

Example for you to try:

| -7  -6  -5  -4  -3 | | -2 |   | -5 |
| -6  -2  -1   0   1 | | -1 |   | 21 |
| -5  -1   2   3   4 | |  0 | = | 42 |
| -4   0   3   5   6 | |  1 |   | 55 |
| -3   1   4   6   7 | |  7 |   | 60 |

To get the quadratic form do a dot product with the multiplication result vector x·A·y = Dot(x,A*y)

Answer 3

Making matrix multiplication as fast as possible is easy: Use a well-known library. Insane amounts of performance work has gone into such libraries. You cannot compete with that.