Подпрограмма:  AMMIR (модуль AMMIR_p)

Назначение

Символическое умножение прямоугольных разреженных матриц, заданных в формате RR (C) U .

Математическое описание

Описание формата RR (C) U приведено в описании подпрограммы AMTSR .

Пусть в формате RR (C) U заданы матрица A размеров  p  на  q  и матрица B размеров  q  на  r. Результирующая матрица C, являющаяся произведением матриц A и B, имеет размеры  p  на  r, а ее элементы определяются формулой

                  q 
     ci k  =   ∑   a i j bj k ,       i = 1, 2,..., p ;      k = 1, 2,..., r
                 j =1 

Эта формула выражает элемент  c_i k  как скалярное произведение  i - й строки матрицы A на  k - й столбец матрицы B. Однако поскольку матрица B задана строчным форматом, то к ее столбцам нет непосредственного доступа. Эту трудность можно обойти путем изменения порядка вычислений попарных произведений при вычислении  c_i k : при фиксированных  i  и  j  элемент  a _i j  умножается на все элементы  b_j k  j - й строки матрицы B; полученные произведения прибавляются к соответствующим компонентам вещественного вспомогательного массива X, начальные значения которых равны нулю. Когда таким образом обработаны все элементы  i - й строки матрицы A, массив X содержит полную  i - ю строку матрицы C. Поясним этот алгоритм на примере умножения матриц второго порядка:

            |  a11     a12  |    |  b11     b12  |           |  c11     c12  |
            |  a21     a22  |    |  b21     b22  |    =     |  c21     c22  | 

По определению имеем:

            c11  =  a11 b11  +  a12 b21
            c12  =  a11 b12  +  a12 b22
            c21  =  a21 b11  +  a22 b21
            c22  =  a21 b12  +  a22 b22 

Изменим порядок вычислений попарных произведений следующим образом:

                  x1  = a11 b11
                  x2  = a11 b12
                  x1  = x1 + a12 b21
                  x2  = x2 + a12 b22
                  c11 = x1
                  c12 = x2
                  x1  = a21 b11
                  x2  = a21 b12
                  x1  = x1 + a22 b21
                  x2  = x2 + a22 b22
                  c21 = x1
                  c22 = x2 

Отметим, что в описанном алгоритме каждый элемент матрицы A последовательно умножается на все элементы каждой строки матрицы B, которые легко доступны, поскольку матрица B задана в строчном формате.

Естественно разбить алгоритм на два этапа - символический и численный.

Результирующая матрица C получается в неупорядоченном формате RR (C) U, даже если представления матриц A и B были упорядочены. Чтобы упорядочить представление матриц, можно дважды применить алгоритм численного транспонирования (подпрограмма AMTSR ). Можно также упорядочить только портрет матрицы C двойным применением алгоритма символического транспонирования (подпрограмма AMTCR ), а затем уже применить алгоритм численного умножения. Так как при численном умножении формат представления матрицы C не меняется, то конечный результат будет упорядоченным.

Число операций умножения в данном алгоритме определяется формулой

                          q 
       n (AB)  =   ∑   n ( ai )  n ( bi ) ,
                         i =1 

где  n ( a_i ) и  n ( b_i ) - количество ненулевых элементов в  i - х строках матриц A и B соответственно. Число сложений будет примерно таким же, если засчитывать сложения с нулями.

С.Писсанецки. Технология разреженных матриц. - М.: Мир, 1988.

Использование

procedure AMMIR(var IA :Array of Integer; var JA :Array of Integer;
                var IB :Array of Integer; var JB :Array of Integer;
                NP :Integer; NQ :Integer; NR :Integer;
                var IC :Array of Integer; var JC :Array of Integer;
                var IX :Array of Integer); 

   Параметры 

   Версии:  нет 

   Вызываемые подпрограммы  нет 

   Замечания по использованию   нет 

Пример использования

Unit TAMMIR_p;
interface
uses
SysUtils, Math, { Delphi }
LStruct, Lfunc, UtRes_p, AMMIR_p;

function TAMMIR: String; 

implementation

function TAMMIR: String;
var
NP,NQ,NR,_i :Integer;
IC :Array [0..4] of Integer;
JC :Array [0..3] of Integer;
IX :Array [0..2] of Integer;
const
IA :Array [0..4] of Integer = ( 1,4,4,6,7 );
JA :Array [0..5] of Integer = ( 1,5,4,4,2,1 );
IB :Array [0..5] of Integer = ( 1,2,4,6,6,7 );
JB :Array [0..5] of Integer = ( 2,2,1,2,1,2 );
begin
Result := '';

{      ТЕСТ ДЛЯ ПОДПРОГРАММЫ AMMIR }

NP := 4;
NQ := 5;
NR := 3;
AMMIR(IA,JA,IB,JB,NP,NQ,NR,IC,JC,IX);
Result := Result + Format('%s',[' IC=']);
Result := Result + #$0D#$0A;
for _i:=0 to 4 do
 begin
  Result := Result + Format('%4d ',[IC[_i]]);
  if ( ((_i+1) mod 5)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[' JC=']);
Result := Result + #$0D#$0A;
for _i:=0 to 3 do
 begin
  Result := Result + Format('%4d ',[JC[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TAMMIR',Result);  { вывод результатов в файл TAMMIR.res }
exit;
end;

end.

Результаты:

       IC  =  ( 1, 2, 2, 4, 5 )
       JC  =  ( 2, 2, 1, 2 )