Подпрограмма:  AMMIR

Назначение

Символическое умножение прямоугольных разреженных матриц, заданных в формате 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

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

    SUBROUTINE  AMMIR ( IA, JA, IB, JB, NP, NQ, NR, IC, JC, IX) 

   Параметры 

   Версии:  нет 

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

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

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

      DIMENSION  IA(5), JA(6), IB(6), JB(6), IC(5), JC(4), IX(3)
      DATA  IA /1, 4, 4, 6, 7/,
     *           JA /1, 5, 4, 4, 2, 1/,
     *           IB /1, 2, 4, 6, 6, 7/,
     *           JB /2, 2, 1, 2, 1, 2/
      NP = 4
      NQ = 5
      NR = 3
      CALL  AMMIR (IA, JA, IB, JB, NP, NQ, NR, IC, JC, IX)

Результаты:

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