Текст подпрограммы и версий ( Фортран )
ammkr.zip 		Тексты тестовых примеров ( Фортран )
tammkr.zip
Текст подпрограммы и версий ( Си )
ammkr_c.zip 		Тексты тестовых примеров ( Си )
tammkr_c.zip
Текст подпрограммы и версий ( Паскаль )
ammkr_p.zip 		Тексты тестовых примеров ( Паскаль )
tammkr_p.zip

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

Назначение

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

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

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

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

                    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 вычисляет портрет результирующей матрицы X, в формате RR (C) U, т.е. реализует символический этап рассмотренного здесь алгоритма

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

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

    SUBROUTINE  AMMKR ( IUT, JUT, IB, JB, NR, NC, IX, JX, 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, используемый в подпрограмме в качестве рабочего 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию:   нет

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

      DIMENSION  IUT(5), JUT(5), IB(5), JB(5), IX(5), JX(8), IP(3)
      DATA  IUT /1, 1, 1, 2, 4/,
     *           JUT /2, 3, 1/,
     *           IB /1, 3, 4, 5, 6/,
     *           JB /3, 1, 2, 1, 3/
      NR = 4
      NC = 3
      CALL  AMMKR (IUT, JUT, IB, JB, NR, NC, IX, JX, IP)

Результаты:

       IX  =  ( 1, 3, 4, 6, 9 )
       JX  =  ( 3, 1, 2, 1, 2, 3, 1, 2 )