ВУЗ:
Составители:
31
Связь LEFT в BASEROW[i] указывает на самый правый узел в
i-й строке и связь UP в BASECOL[ j] – на самый нижний узел в j-м столбце.
Например, матрица
−− 560030
0000
020010
00050
(28)
будет представлена так, как показано на рис. 7.
Рис. 7. Машинное представление разреженной матрицы
При последовательном распределении памяти эта матрица заняла бы
больше слов, а при увеличении её размеров экономия становится ещё
более существенной. При этом время, расходуемое на доступ к произ-
вольному элементу матрицы, остаётся в разумных пределах, поскольку в
каждой строке и каждом столбце встречается немного элементов. Кроме
того, в большинстве матричных алгоритмов осуществляется последова-
тельное прохождение матрицы и поэтому связанное представление при-
водит к незначительной потере скорости работы.
В качестве характерного примера рассмотрим операцию осевого ша-
га для разреженных матриц, которая играет важную роль в алгоритмах
решения систем линейных уравнений, обращения матриц и линейного
программирования (симплекс-метод):
-1
-1
1 1 50
1 2 10
1 4 -30
3 2 20
3 4 -60
4 4 5
-1
-1
-1
-1
-1
-1
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
