Текст подпрограммы и версий
ammkr_c.zip 		Тексты тестовых примеров
tammkr_c.zip

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

Назначение

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

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

Сокращенное наименование формата RR (L) U происходит от английского словосочетания "Row - wise Representation, Lower, Unordered" (строчное представление, нижний треугольник, неупорядоченное). Данный формат отличается от формата RR (U) U (см. описание подпрограммы am21r_c ), только тем, что в нем представлены элементы нижнего, а не верхнего треугольника. Описание формата RR (C) U приведено в описании подпрограммы amtsr_c .

Операция, выполняемая подпрограммой ammkr_c, эквивалентна следующей операции: 

                    X = U -TB ,

где B - прямоугольная разреженная матрица с NR строками и NC столбцами, заданная в формате RR (C) U, U - верхняя треугольная разреженная матрица порядка NR с единичной диагональю, заданная в формате RR (U) U, X - результирующая прямоугольная разреженная матрица с NR строками и NC столбцами, формируемая в формате RR (C) U. Так как UT - нижняя треугольная матрица, то она задается в формате RR (L) U.

Матрица X может быть найдена без вычисления обратной для матрицы UT, которая была бы плотной матрицей. Для этого рассмотрим эквивалентное соотношение UTX = B. Полученная система линейных уравнений решается символическим и численным алгоритмами с привлечением вспомогательных массивов. Поясним численный алгоритм на примере: 

            |   1   0   0   |      |   x11    x12   |     =     |   b11    b12   |
            |   a   1   0   |      |   x21    x22   |     =     |   b21    b22   |
            |   b   c   1   |      |   x31    x32   |     =     |   b31    b32   |

Для первой строки имеем ( x11, x12 )  =  ( b11, b12 ), откуда следует, что  x11  =  b11,  x12  =  b12. Для второй строки: 

            a ( x11, x12 ) + ( x21, x22 )  =  ( b21, b22 ) 
Следовательно,
              ( x21, x22 )  =  ( b21, b22 ) - a ( x11, x12 )

Аналогично получаем для третьей строки: 

              ( x31, x32 )  =  ( b31, b32 ) - b ( x11, x12 ) - c ( x21, x22 )

Выписанные уравнения решаются последовательно и в результате получается матрица X. Этот алгоритм приспособлен для разреженных матриц, заданных в строчном формате.

Подпрограмма ammkr_c вычисляет портрет результирующей матрицы X, в формате RR (C) U, т.е. реализует символический этап рассмотренного здесь алгоритма

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

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

    int ammkr_c (integer *iut, integer *jut, integer *ib,
            integer *jb, integer *nr, integer *nc, integer *ix, integer *jx,
            integer *ip)

   Параметры
iut, jut - заданный портрет матрицы UT в формате RR (L) U;
ib, jb - заданный портрет матрицы B в формате RR (C) U;
nr - заданный порядок матрицы UT и число строк матриц B и X (тип: целый);
nc - заданное число столбцов матриц B и X (тип: целый);
ix, jx - вычисленный портрет результирующей матрицы X в формате RR (C) U;
ip - целый массив длины nc, используемый в подпрограмме в качестве рабочего 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию:   нет

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

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

    /* Local variables */
    extern int ammkr_c(int *, int *, int *, int *, int *, int *,
                       int *, int *, int *);
    static int nc, ip[3], nr, ix[5], jx[8];

    nr = 4;
    nc = 3;
    ammkr_c(iut, jut, ib, jb, &nr, &nc, ix, jx, ip);

    printf("\n %5i %5i %5i %5i %5i \n", ix[0], ix[1], ix[2], ix[3], ix[4]);
    printf("\n %5i %5i %5i %5i %5i %5i %5i %5i \n",
           jx[0], jx[1], jx[2], jx[3], jx[4], jx[5], jx[6], jx[7]);
    return 0;
} /* main */

Результаты:

       ix  =  ( 1, 3, 4, 6, 9 )
       jx  =  ( 3, 1, 2, 1, 2, 3, 1, 2 )