Сделать эффективным — симметричное матричное умножение с двумя векторами в С#

В соответствии с начальным потоком сделайте эффективной копию симметричного матрица до-диез от cMinor.

Мне было бы очень интересно узнать, как построить умножение симметричной квадратной матрицы с одним линейным вектором и одним вектором-столбцом, используя реализацию матрицы в виде массива вместо классического

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];
    }
}

Спасибо за ваш вклад!


c# performance matrix vector matrix-multiplication
person Seb T.    schedule 23.05.2012    source источник

Ответы (3)


arrow_upward
7
arrow_downward

Линейный вектор, умноженный на симметричную матрицу, равен транспонированию матрицы, умноженной на вектор-столбец. Таким образом, необходимо рассматривать только случай вектора-столбца.

Первоначально i-й элемент y=A*x определяется как

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

но так как A симметрично, сумма будет разделена на суммы, одна ниже диагонали, а другая выше

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

Из другой проводки индекс матрицы

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

Для N×N симметричной матрицы A = new double[N*(N+1)/2];

В коде C# приведенное выше:

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++;
    }
}

Пример для вас, чтобы попробовать:

| -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 |

Чтобы получить квадратичную форму, выполните скалярное произведение с вектором результата умножения x·A·y = Dot(x,A*y)

person John Alexiou    schedule 23.05.2012
comment
Спасибо за этот довольно подробный ответ и за предоставление кода, я многому научился за несколько строк. - person Seb T.; 24.05.2012
comment
Просто небольшое подтверждение моего понимания. В этом конкретном случае, используя квадратную симметричную матрицу, мы можем рассматривать оба вектора как векторы-столбцы (которые мы можем назвать x & x '). Это означает, что если я хочу получить результат умножения для обоих векторов, я могу сделать это за один раз, используя приведенный ниже диагональный код как y[i]+=A[k]*x[j]*x'[j]; и так далее по вышеуказанной диагонали. Я прав ?! - person Seb T.; 24.05.2012
comment
Ну, вы бы не рассматривали x и x' в одной и той же операции. Таким образом, утверждение y[i]+=A[k]*x[j]*x'[j] недопустимо. Возможно, вам нужно включить в исходную публикацию пример того, что вы пытаетесь сделать. Обычно вы делаете что-то вроде scalar = x'*A*x. - person John Alexiou; 24.05.2012
comment
Учтите также, что произведение двух симметричных матриц не является симметричным. - person John Alexiou; 24.05.2012

arrow_upward
4
arrow_downward

Вы можете сделать умножение матриц довольно быстро с помощью небезопасного кода. Я написал об этом в блоге.

person Darin Dimitrov    schedule 23.05.2012
comment
Правильный. Если цель — скорость, небезопасным будет путь. Если объект имеет уменьшенный размер, то подход с уменьшенным элементом, указанный в OP, - это путь. - person John Alexiou; 23.05.2012
comment
Интересно, как unsafe соотносится с упакованным массивом в моем посте. Наивный подход в вашем блоге использует 2D-массив, который, как известно, работает медленно, и его следует избегать. Самый быстрый подход — это зубчатые массивы, затем упакованные массивы, а затем собственные 2D-массивы. - person John Alexiou; 30.07.2019

arrow_upward
0
arrow_downward

Сделать умножение матриц как можно быстрее легко: используйте известную библиотеку. В такие библиотеки вложено безумное количество производительности. Вы не можете конкурировать с этим.

person usr    schedule 23.05.2012