Текст подпрограммы и версий ( Фортран )
amtsr.zip , amtsd.zip
Тексты тестовых примеров ( Фортран )
tamtsr.zip , tamtsd.zip
Текст подпрограммы и версий ( Си )
amtsr_c.zip , amtsd_c.zip
Тексты тестовых примеров ( Си )
tamtsr_c.zip , tamtsd_c.zip
Текст подпрограммы и версий ( Паскаль )
amtsr_p.zip , amtse_p.zip
Тексты тестовых примеров ( Паскаль )
tamtsr_p.zip , tamtse_p.zip

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

Назначение

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

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

Рассмотрим сначала формат RR (C) O.

Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Ordered" (строчное представление, полное и упорядоченное).

Значения ненулевых элементов матрицы и соответствующие им столбцовые индексы хранятся в этом формате по строкам в двух массивах AN и JA. Используется также массив указателей IA, указывающих компоненты массивов AN и JA, с которых начинается описание очередной строки. Последняя компонента массива IA содержит указатель первой свободной компоненты в массивах AN и JA, т.е. равна числу ненулевых элементов матрицы, увеличенному на единицу. Поясним сказанное на примере.

Рассмотрим матрицу A с тремя строками и десятью столбцами:

                     1     2    3     4      5      6      7      8      9    10 

              1    | 0    0   1.0   3.0   0      0      0     5.0    0     0   |
      A =  2    | 0    0    0     0      0      0      0      0      0     0   |
              3    | 0    0    0     0      0     7.0    0     1.0    0     0   |

В формате RR (C) O матрица A представляется следующим образом:

             IA  =  (1, 4, 4;   6) 
             JA  =  (3, 4, 8;   6,8) 
           AN  =  (1.0, 3.0, 5.0;   7.0, 1.0) 

Значения ненулевых элементов первой строки матрицы A и их столбцовых индексов начинаются с компонент массивов AN и JA, номера которых определяются первой компонентой массива IA. В данном примере - с первых компонент массивов AN и JA, поскольку IA (1) = 1.

Информация о второй строке матрицы A указывается в массивах AN и JA с компонент, номера которых определяются второй компонентой массива IA, т.е. с компонент с номером 4, поскольку IA (2) = 4. Аналогично, третья строка матрицы A определяется компонентами массивов AN и JA начиная с AN(4) и JA(4), поскольку IA (3) = 4. Заметим, что IA (2) = IA (3) = 4, а это означает, что вторая строка матрицы A нулевая.

Последняя, четвертая компонента массива IA, равная 6 (IA (4) = 6)), указывает номер первой свободной компоненты массивов AN и JA, начиная с которой информация о матрице A отсутствует. Это означает, что описание последней, третьей строки матрицы A заканчивается в компонентах с номером IA (4) - 1 = 5 массивов AN и JA.

В общем случае описание r - й строки матрицы A хранится в компонентах с IA (r) до IA (r + 1) - 1 массивов AN и JA. Если IA (r + 1) = IA(r), то это означает, что  r - я строка нулевая. Если матрица A имеет  m строк, то массив IA состоит из (m + 1) - й компоненты.

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

Говорят, что массивы IA и JA представляют портрет (структуру) матрицы A. Если алгоритм, реализующий какую - либо операцию над разреженными матрицами, разбит на этапы символической обработки, на котором определяется портрет результирующей матрицы, и численной обработки, на котором определяются численные значения элементов результирующей матрицы, то массивы IA и JA заполняются на первом этапе, а массив AN - на втором.

Рассмотрим теперь формат RR (C) U.

Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Unordered" (строчное представление, полное, но неупорядоченное).

Формат RR (C) U вводится по следующим причинам. Представления разреженных матриц необязательно должны быть упорядочены в том смысле, что, хотя упорядоченность строк соблюдается, внутри каждой строки элементы исходных матриц могут храниться в произвольном порядке. Такие неупорядоченные представления могут быть весьма удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными. Для приведенной выше матрицы A, например, ее представление в формате RR(C)U может иметь вид:

             IA  =  (1, 4, 4;   6) 
             JA  =  (8, 3, 4;   8,6)
           AN  =  (5.0, 1.0, 3.0;   1.0,7.0) 

После работы подпрограммы AMTSR результирующая транспонированная матрица A представляется в формате RR (C) O.

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

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

    SUBROUTINE  AMTSR (IA, JA, AN, N, M, IAT, JAT, ANT) 

Параметры

IA - целый массив длины N + 1, содержащий указатели компонент массивов JA и AN, с которых начинается описание очередной строки транспонируемой матрицы; последняя компонента массива IA содержит число ненулевых элементов, увеличенное на единицу;
JA - целый массив, содержащий не обязательно в упорядоченном виде номера столбцов ненулевых элементов транспонируемой матрицы по ее строкам, начиная с первой; его длина равна числу ненулевых элементов;
AN - вещественный массив, содержащий ненулевые элементы транспонируемой матрицы по строкам в соответствии с массивом JA; длина AN равна числу ненулевых элементов;
N - заданное число строк транспонируемой матрицы (тип: целый);
M - заданное число столбцов транспонируемой матрицы (тип: целый);
IAT - целый массив длины M + 1, содержащий указатели компонент массивов JAT и ANT, с которых начинается описание очередной строки транспонированной матрицы; последняя компонента массива IAT содержит число ненулевых элементов, увеличенное на единицу;
JAT - целый массив, содержащий в упорядоченном виде номера столбцов ненулевых элементов транспонированной матрицы по ее строкам, начиная с первой; его длина равна числу ненулевых элементов;
ANT - вещественный массив, содержащий ненулевые элементы транспонированной матрицы по строкам в соответствии с массивом JAT; длина ANT равна числу ненулевых элементов

Версии

AMTSD - транспонирование прямоугольной разреженной матрицы, заданной в формате RR (C) U, в режиме удвоенной точности; при этом параметры AN и ANT должны иметь тип DOUBLE PRECISION

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

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

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

      INTEGER IA(6), JA(13), IAT(7), JAT(13) 
      REAL AN(13), ANT(13) 
      DATA IA /1, 4, 6, 8, 11, 14/,
     *           JA /5, 6, 3, 4, 1, 3, 4, 4, 3, 1, 2, 6, 5/
      DATA AN /15., 16., 13., 24., 21., 33., 34., 44., 43., 41., 52., 56., 55./
      N = 5 
      M = 6 
      CALL  AMTSR (IA, JA, AN, N, M, IAT, JAT, ANT) 

Результаты: 
                
        IAT  =  (1, 3, 4, 7, 10, 12, 14) 
        JAT  =  (2, 4, 5, 1, 3, 4, 2, 3, 4, 1, 5, 1, 5) 
      ANT  =  (21, 41, 52, 13, 33, 43, 24, 34, 44, 15, 55, 16, 56)