Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Алгоритм] Умножение матриц

Автор: salat 7.12.2009, 04:50

Уважаемые форумчане, необходима подсказка, а точнее помощь в написании алгоритма. Я уже голову сломал.

Надо умножить матрицу А на матрицу B.

матрица A (R nxn) - симметричная, содержимое храниться только в верхнетреугольной части матрицы.
матрица B (R nxm)- прямоугольная матрица.

Пишу на Си.

Буду благодарен за любую помощь. Заранее спасибо!

Автор: Reaver 7.12.2009, 19:47

Все просто. Данный кусок кода написан на Delphi, но на Си перенести его можно без проблем:

Код


for i := 0 to MatrixB.Col - 1 do begin
  for j := 0 to MatrixA.Row - 1 do
    for k := 0 to MatrixA.Col - 1 do
      Result.element[i, j] := MatrixA.element[k, j] * MatrixB.element[i, k] + Result.element[i, j];
end;

Где:
MatrixB.Col - число столбцов матрицы В
MatrixА.Col - число столбцов матрицы А
MatrixА.Row - число строк матрицы A

Автор: salat 11.12.2009, 00:22

Спасибо. Но этот алгоритм не совсем подходит. Данный алгоритм просто перемножает матрицы. А нужен именно алгоритм способный перемножать обычную прямоугольную матрицу и симметричную матрицу, причем в симметричной матрице, содержимое храниться в верней треугольной части, а нижняя часть, как я понимаю заполнена нулями, т.е. например C = A * B
где:

A { {1, 2, 3} {0, 4, 5} {0, 0, 6} } - симметричная, содержимое храниться только в верхнетреугольной части матрицы.
B { {1, 2} {3, 4} {5, 6} } - прямоугольная матрица.

Вот как то так. Может кто знает ещё алгоритмы?

Автор: bilbobagginz 11.12.2009, 00:50

Цитата(salat @ 10.12.2009, 23:22

)

Может кто знает ещё алгоритмы?

для того, чтобы все это сделать, стоит знать что такое симметричная матрица....
потому как судя по твоему посту ты это еще не знаешь.

а вопрос этот в раздел по алгоритмам не тянет.

Добавлено через 3 минуты и 29 секунд
salat, давай подумаем вместе...
где тут симметрия:

Код


1 2 3
0 4 5
0 0 6

?
эта матрица "верхнеугольная", но не симметричная.

Автор: Reaver 11.12.2009, 17:33

Приведенный выше алгоритм универсален. Абсолютно без разницы, обычные, треугольные или симметричные матрицы ему умножать. Главное, чтоб размерности подходили.

Автор: bilbobagginz 11.12.2009, 23:44

Reaver, возможно имелось в виду оптимизация.
если время вычисления суммы на строке 4 и время доступа до ячеек = О(1), твой алгоритм имеет сложность:
O( MatrixB.Col x MatrixА.Col x MatrixА.Row), или грубо говоря О(n^3).

Возможно при понимании, что матрица симметрична,
циклы сокращаются(т.к. a(i,j)=a(j,i)) и в результате все доходит до более высокой скорости, т.е. столбики можно проходит до половины, а остальное "угадывать".

Автор: salat 12.12.2009, 00:35

Как я понял из задания, что матрица симметричная т.е.

1 2 3
2 4 5
3 5 6

Но, представлена она по хитрому, т.е.

1 2 3
0 4 5
0 0 6

Это значит, что для вычисления значения формулы, нужно обращаться только к тем элементам матрицы, которые находятся выше главной диагонали или на ней. Нижняя часть заполнена нулями и обращаться к этой части нельзя. А симметрия - это типа "подсказки" взадании, что вместо элементов из нижнего треугольника нужно использовать элементы из верхнего треугольника. Т.е. элементы из нижней части, тоже надо использовать при перемножении в результирующей матрице, но только за место них брать верхние при умножении.

P.S. да я согласен, что не силен в матрицах, поэтому и обратился за помощью. И вроде все просто, но возникли трудности. Требуют алгоритм оптимальный, он будет использоваться, для программирования процессора, поэтому и такие условия.

Автор: bilbobagginz 12.12.2009, 18:49

Цитата(salat @ 11.12.2009, 23:35

)

но возникли трудности

покажи свои "трудности", и мы тебе поможем его доработать.

Автор: salat 12.12.2009, 23:13

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

for(i=0;i<3;i++) {
    for(j=0;j<2;j++) {
        for(k=0;k<3;k++) {
            matrix_c[i][j] += matrix_a[i][k] * matrix_b[k][j];
        }
    }
}

Первые два прохода j (т.е. первая строка результирующей матрицы - matrix_c[0][0] и matrix_c[0][1]) всё ок, ну это и понятно, но дело доходит до второй строки и в матрице А("симметричной") присутствует ноль(matrix_a[1][0]), но вместо этого нуля нужно брать так скажем "симметричный" ему элемент, т.е. 2-ку - matrix_a[0][1](опять же рассматривая описанный выше пример). Но записывать результат в  matrix_c[1][0]. Дальше не описываю, т.к. надеюсь мысль ясна. В итоге должна получиться матрица matrix_c размерностью 3х2. Ну как и с обычным перемножением. Вот собственно в организации такого алгоритма и состоит трудность.

Автор: bilbobagginz 13.12.2009, 03:51

ты не заметил, что "симметричный" элемент элементу i,j - элемент j,i.
у тебя в левой матричке даны только элементы i,j, так, что i<=j. остальные - 0.

Добавлено через 13 минут и 29 секунд

Код


            for (i=0;i<l->height;i++){
                for (j=0;j<r->width;j++){
                    result->data[i][j]=0;
                    for (k=0;k<(l->width);k++){
                        if (i<=j){
                            result->data[i][j]+=(l->data[i][k])*(r->data[k][j]);
                        }
                        else{
                            result->data[i][j]+=(l->data[k][i])*(r->data[k][j]);
                        }
                    }
                }

            }

Автор: salat 13.12.2009, 23:40

К сожалению, и этот алгоритм не работает((

Автор: salat 14.12.2009, 00:35

В итоге получился вот такой алгоритм, вроде работает, но не проверял ещё, только на бумаге))

       for(i=0; i<NSIZE; i++){
        for(j=0; j<MSIZE; j++){
            D[i][j] = 0.0;
            for(k=0; k<NSIZE; k++){
                if(i=0){
                    D[i][j] += (A[i][k]*B[k][j]);
                }
                else if(k<=i){
                    D[i][j] += (A[k][i]*B[k][j]);
                }
                else D[i][j] += (A[i][k]*B[k][j]);
            }
        }
    }

Правда условий мне кажется слишком много.... может как-нить его упростить можно...

Спасибо bilbobagginz за помощь!!!

Автор: bilbobagginz 14.12.2009, 01:06

Цитата(salat @ 13.12.2009, 22:40

)

К сожалению, и этот алгоритм не работает((

это не алгоритм а код.
в каком случае мой код дает неверный ответ?

Цитата(salat @ 13.12.2009, 23:35

)

if(i=0){

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

Код


if (0=i) {

такой код не скомпилируется и выйдет ошибка. т.к. надо было писАть ==.
твой код - скомпилируется, и будешь отлавливать. суслика в поле.

Автор: salat 14.12.2009, 01:30

Да уж это точно, по запаре написал... не о синтаксисе думал...

В твоем коде, на элементе [1][0] в результирующей матрице, на 3-м проходе k, обращение происходит к A[2][1] который равен 0, ну и так далее...

Автор: bilbobagginz 14.12.2009, 04:18

Цитата(salat @ 14.12.2009, 00:30

)

В твоем коде, на элементе [1][0] в результирующей матрице, на 3-м проходе k, обращение происходит к A[2][1] который равен 0, ну и так далее...

блин я спутал, проверка должна быть:

Код


 if (i<=k){

тоже торможу smile

Автор: salat 14.12.2009, 23:47

Да точно)) а я там наворотил лишнее условие))

В итоге получилось так:

Код


for(i=0; i<NSIZE; i++){
     for (j=0; j<MSIZE; j++){
         D[i][j] = 0.0;
            for(int k=0; k<NSIZE; k++){
             if (i<=k){
                    D[i][j] += A[i][k]*B[k][j];
                }
                else{
                    D[i][j] += A[k][i]*B[k][j];
                }
            }
        }
}

Получается мы проходим по элементам "симметричной" матрицы под прямым углом, т.е. по столбцу до элемента расположенного на диагонали, а потом по строке, от него. Щас другая задача - убрать if и сделать все это дело через for и будет счастье))