"Комплект" заданий по численным методам — страница 8

  • Просмотров 2992
  • Скачиваний 431
  • Размер файла 32
    Кб

Разреженный строчный формат Это одна из широко используемых схем для хранения разреженных матриц, которая предъявляет минимальные требования к памяти и очень удобна для выполнения основных операций с матрицами. Значения ненулевых элементов и соответствующие столбцовые индексы хранятся по строкам в двух массивах: NA и JA. Для разметки строк в этих массивах используется массив указателей IA, отмечающих позиции массивов AN и JA, с

которых начинается описание очередной строки. Пос- ледняя цифра в массиве IA содержит указатель первой свободной позиции в JA и AN. Рассмотрим конкретный пример, который будет также и далее применятся для демонстрации других операций и который был использован в качестве контрольного примера для программы, выполняющей основные операции с разреженными матрицами. ┌ ┐ │ 3 0 0 5 0 │ Позиция: 1 2 3 4 5 6 7 8 9 10 │ 0 4 0 0 1 │ IA: 1 3 5 7 9 11 A =

│ 0 0 8 2 0 │ JA: 1 4 2 5 3 4 1 4 2 5 │ 5 0 0 6 0 │ AN: 3 5 4 1 8 2 5 6 7 9 │ 0 7 0 0 9 │ └ ┘ Данный способ представления называется полным (так как представ- лена вся матрица А) и упорядоченным (так как элементы каждой строки хранятся в соответствии с возрастанием столбцовых индексов). Обознача- ется RR(c)O - Row-wise representation Complete and Ordered (англ.). Массивы IA и JA представляют портрет матрицы А. Если в алгоритме разграничены этапы символической и численной

обработки, то массивы IA и JA заполняются на первом этапе, а массив AN - на втором. Транспонирование разреженной матрицы Пусть IA, JA, AN - некоторое представление разреженной матрицы. Нужно получить IAT, JAT, ANT - разреженное представление транспониро- ванной матрицы. Алгоритм рассмотрим на нашем примере: IA = 1 3 5 7 9 11 JA = 1 4 2 5 3 4 1 4 2 5 AN = 3 5 4 1 8 2 5 6 7 9 Символический этап. 1. Заводим 5 целых списков по числу столбцов матрицы А. пронуме- руем их от 1 до 6. 2.

Обходим 1 строку и заносим 1 в те списки, номера которых ука- заны в JA: 1: 1 2: 3: 4: 1 5: 3. Обходим вторую строку, вставляя аналогичным образом 2: 1: 1 2: 2 3: 4: 1 5: 2 В итоге получим: 1: 1 4 2: 2 5 3: 3 4: 1 3 4 5: 2 5 Массив ANT можно получить, вставляя численное значение каждого ННЭ, хранимое в AN, в вещественный список сразу после того, как соот- ветствующее целое внесено в целый список. В итоге получим: IAT = 1 3 5 6 9 11 JAT = 1 4 2 5 3 1 3 4 2 5 ANT = 3 5 4 7 8 5 2 6 1 9 Произведение

разреженной матрицы и заполненного вектора-столбца Алгоритм рассмотрим на нашем конкретном примере: IAT = 1 3 5 7 9 11 JAT = 1 4 2 5 3 1 3 4 2 5 ANT = 3 5 4 7 8 5 2 6 1 9 B = ( -5 4 7 2 6 ) Обработка 1 строки: Просматриваем массив IA и обнаруживаем, что первая строка матрицы А соответствует первому и второму элементу массива JA: JA(1)=3, JA(2)=4, то есть ННЭ являются a 411 0 и a 414 0. Просматриваем массив AN и устанавливаем, что a 411 0=3 и a 414 0=5. Обращаемся к вектору