|
Текст подпрограммы и версий amtsr_p.zip , amtse_p.zip |
Тексты тестовых примеров tamtsr_p.zip , tamtse_p.zip |
Транспонирование прямоугольной разреженной матрицы, заданной в формате 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.
procedure AMTSR(var IA :Array of Integer; var JA :Array of Integer;
var AN :Array of Real; N :Integer; M :Integer;
var IAT :Array of Integer; var JAT :Array of Integer;
var ANT :Array of Real);
Параметры
| IA - | целый массив длины N + 1, содержащий указатели компонент массивов JA и AN, с которых начинается описание очередной строки транспонируемой матрицы; последняя компонента массива IA содержит число ненулевых элементов, увеличенное на единицу; |
| JA - | целый массив, содержащий не обязательно в упорядоченном виде номера столбцов ненулевых элементов транспонируемой матрицы по ее строкам, начиная с первой; его длина равна числу ненулевых элементов; |
| AN - | вещественный массив, содержащий ненулевые элементы транспонируемой матрицы по строкам в соответствии с массивом JA; длина AN равна числу ненулевых элементов; |
| N - | заданное число строк транспонируемой матрицы (тип: целый); |
| M - | заданное число столбцов транспонируемой матрицы (тип: целый); |
| IAT - | целый массив длины M + 1, содержащий указатели компонент массивов JAT и ANT, с которых начинается описание очередной строки транспонированной матрицы; последняя компонента массива IAT содержит число ненулевых элементов, увеличенное на единицу; |
| JAT - | целый массив, содержащий в упорядоченном виде номера столбцов ненулевых элементов транспонированной матрицы по ее строкам, начиная с первой; его длина равна числу ненулевых элементов; |
| ANT - | вещественный массив, содержащий ненулевые элементы транспонированной матрицы по строкам в соответствии с массивом JAT; длина ANT равна числу ненулевых элементов. |
Версии
| AMTSE - | транспонирование прямоугольной разреженной матрицы, заданной в формате RR (C) U, в режиме расширенной (Extended) точности; при этом параметры AN и ANT должны иметь тип Extended. |
Вызываемые подпрограммы: нет
Замечания по использованию: нет
Unit TAMTSR_p;
interface
uses
SysUtils, Math, { Delphi }
LStruct, Lfunc, UtRes_p, AMTSR_p;
function TAMTSR: String;
implementation
function TAMTSR: String;
var
N,M,_i :Integer;
IАТ :Array [0..6] of Integer;
JАТ :Array [0..12] of Integer;
ANT :Array [0..12] of Real;
const
IA :Array [0..5] of Integer = ( 1,4,6,8,11,14 );
JA :Array [0..12] of Integer = ( 5,6,3,4,1,3,4,4,3,1,2,6,5 );
AN :Array [0..12] of Real = ( 15.0,16.0,13.0,24.0,21.0,33.0,34.0,44.0,43.0,
41.0,52.0,56.0,55.0 );
begin
Result := '';
{ ТЕСТ ДЛЯ ПРОГРАММЫ AMTSR }
N := 5;
M := 6;
AMTSR(IA,JA,AN,N,M,IAT,JAT,ANT);
Result := Result + Format('%s',[' IAT=']);
Result := Result + #$0D#$0A;
for _i:=0 to 6 do
begin
Result := Result + Format('%5d ',[IAT[_i]]);
if ( ((_i+1) mod 15)=0 )
then Result := Result + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[' JAT=']);
Result := Result + #$0D#$0A;
for _i:=0 to 12 do
begin
Result := Result + Format('%5d ',[JAT[_i]]);
if ( ((_i+1) mod 15)=0 )
then Result := Result + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[' ANT=']);
Result := Result + #$0D#$0A;
for _i:=0 to 12 do
begin
Result := Result + Format('%20.16f ',[ANT[_i]]);
if ( ((_i+1) mod 5)=0 )
then Result := Result + #$0D#$0A;
end;
Result := Result + #$0D#$0A;
UtRes('TAMTSR',Result); { вывод результатов в файл TAMTSR.res }
exit;
end;
end.
Результаты:
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)