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

Назначение

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

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

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

Пусть в формате 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 ). Можно также упорядочить только портрет матрицы C двойным применением алгоритма символического транспонирования (подпрограмма amtcr_c ), а затем уже применить алгоритм численного умножения. Так как при численном умножении формат представления матрицы C не меняется, то конечный результат будет упорядоченным.

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

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

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

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

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

    int ammir_c (integer *ia, integer *ja, integer *ib,
                 integer *jb, integer *np, integer *nq, integer *nr, integer *ic,
                 integer *jc, integer *ix)

   Параметры 

   Версии:  нет 

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

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

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

int main(void)
{
    /* Initialized data */
    static int ia[5] = { 1,4,4,6,7 };
    static int ja[6] = { 1,5,4,4,2,1 };
    static int ib[6] = { 1,2,4,6,6,7 };
    static int jb[6] = { 2,2,1,2,1,2 };

    /* Local variables */
    extern int ammir_c(int *, int *, int *, int *, int *, int *,
                       int *, int *, int *, int *);
    static int ic[5], jc[4], np, nq, nr, ix[3];

    np = 4;
    nq = 5;
    nr = 3;
    ammir_c(ia, ja, ib, jb, &np, &nq, &nr, ic, jc, ix);

    printf("\n %5i %5i %5i %5i %5i \n", ic[0], ic[1], ic[2], ic[3], ic[4]);
    printf("\n %5i %5i %5i %5i \n", jc[0], jc[1], jc[2], jc[3]);
    return 0;
} /* main */


Результаты:

       ic  =  ( 1, 2, 2, 4, 5 )
       jc  =  ( 2, 2, 1, 2 )