Форматы представления разреженных матриц

Представление разреженных матриц.

Разглядим форматы представления разреженных матриц, т.е. матриц имеющих огромное число нулевых частей. В данном случае обыденное представление матриц в виде массива будет сверхизбыточно, потому употребляются особые форматы: RR(C)O и RR(C)U. Разглядим поначалу формат RR(C)O. Сокращенное заглавие данного формата происходит Форматы представления разреженных матриц от британского словосочетания "Row - wise Representation Complete and Ordered" (строчное представление, полное и упорядоченное). В данном формате заместо 1-го двумерного массива, употребляются три одномерных. Значения ненулевых частей матрицы и надлежащие им столбцовые индексы хранятся в этом формате по строчкам в 2-ух массивах AN и JA. Массив указателей IA, употребляется Форматы представления разреженных матриц для ссылки на составляющие массивов AN и JA, с которых начинается описание очередной строчки. Последняя компонента массива IA содержит указатель первой свободной составляющие в массивах AN и JA, т.е. равна числу ненулевых частей матрицы, увеличенному на единицу.

Проще всего разобраться с представлением на примере, пусть A матрица с Форматы представления разреженных матриц 3-мя строчками и 10 столбцами:

3.2 1.5 7.3
8.5 9.8

тогда ее представление в формате RR(C)O будет иметь вид:

IA = ( 1, 4, 4, 6)
JA = ( 2, 4, 8, 6, 8)
AN = ( 3.2, 1.5, 7.3, 8.5, 9.8)

Т.е. массив AN содержит все не нулевые элементы начальной матрицы A, массив JA номер столбца в каком находится соответственный элемент из AN и в конце концов массив IA содержит номер с Форматы представления разреженных матриц которого начинается описание частей в массивах JA и AN. Таким макаром информация об элементах 3 строчки матрицы храниться в элементах с IA[3]=4 по IA[4]-1=5 массивов JA и AN. Заметим, что IA(2)=IA(3)=4, а это значит, что 2-ая строчка матрицы A нулевая.

В общем случае описание r-й строчки матрицы A хранится в Форматы представления разреженных матриц компонентах с IA[r] до IA[r + 1]-1 массивов AN и JA. Если IA[r + 1] = IA[r], то это значит, что r - я строчка нулевая. Количество частей в массиве IA на единицу больше, чем число строк начальной матрицы, а количество частей в массивах JA и AN равно Форматы представления разреженных матриц числу ненулевых частей начальной матрицы.

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

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

Разглядим сейчас формат RR(C)U.

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

IA = ( 1, 4, 4, 6)
JA = ( 4, 2, 8, 6, 8)
AN = ( 1.5, 3.2, 7.3, 8.5, 9.8)

Несколько замечаний по поводу рассмотренных форматов представления.

1-ое. Понятно, что представление матрицы в формате RR(C)O так же является и представлением в формате RR(C)U, но не напротив.

2-ое. Из представления Форматы представления разреженных матриц матрицы в формате RR(C) нельзя получить информацию о количестве столбцов начальной матрицы. Вправду, если с количеством строк все довольно ясно, их на единицу меньше, чем частей массива IA, то единственно, что мы можем сказать относительно числа столбцов, это то, что их не больше чем максимум посреди всех частей Форматы представления разреженных матриц массива JA. К примеру, возьмем матрицу рассмотренную выше, на базе представления в формате RR(C)U мы можем сказать только, что столбцов не меньше 8, но ни что не показывает нам на то, что их ровно 10.

Третье. Целенаправлено использовать представления RR(C) в случае, если матрица содержит Форматы представления разреженных матриц существенное число нулевых частей. Получим связь меж числом ненулевых частей начальной матрицы и экономией памяти при использовании форматов RR(C).

Пусть дана матрица A размера NxM, содержащая NNZ не нулевых частей. Положим для хранения значения элемента матрицы мы используем u - б памяти, для хранения номера строчки/стобца - v - б. Тогда Форматы представления разреженных матриц для хранения матрицы в обыкновенном формате нам пригодиться u*N*M б, а для хранения в формате RR(C) v*(N+1)+(u+v)*NNZ. И как следует, представление в формате RR(C) целенаправлено использовать в случае когда, NNZ < (uNM-vN-v)/(u+v).

Так если элементы матрицы действительные Форматы представления разреженных матриц числа(тогда обычно u=8) и число строк и столбцов не превосходит 255(v=1), то получаем оценку NNZ < (8NM-N-1)/9. Так вновь возращаясь например, описанному чуть повыше, получаем, что число ненулевых частей не должно превосходить (8*10*3-10-1)/9=25. А в нашем случае, когда NNZ=5 получаем экономию 8*10*3-(4+5*(8+1))=191 б.


forma-secheniya-stupici-gost-1139-80.html
forma-soglasiya-dlya-poruchitelyazalogodatelya-yuridicheskogo-lica.html
forma-specialnogo-recepturnogo-blanka-na-narkoticheskoe-lekarstvennoe-sredstvo-prednaznachena-dlya-propisivaniya-lekarstvennih-preparatov.html