ВУЗ:
Составители:
Рубрика:
- 3 -
§ 1. Введение
Строгого определения разреженной матрицы нет, но есть “нестрогие”
определения, некоторые из которых мы здесь приведем.
О п р е д е л е н и е 1.1. Разреженная матрица ( РМ ) – это матрица , у
которой “много” элементов равно нулю .
О п р е д е л е н и е 1.2. Разреженная матрица – это матрица , для
которой использование алгоритмов , учитывающих наличие нулей, позволяет
добиться экономии машинного времени и памяти по сравнению с
традиционными методами.
РМ возникают при решении многих прикладных задач . Назовем некоторые
из них:
1) дискретизация уравнений математической физики – разностные схемы и
метод конечных элементов;
2) задачи линейного программирования (теория оптимизации);
3) задачи теории электрических цепей.
Основная задача курса – научиться строить эффективные алгоритмы
решения систем линейных алгебраических уравнений (СЛАУ)
f
AU
=
(
A
– РМ), т.е. пытаться оптимизировать процесс решения с точки зрения
затрат машинной памяти и времени .
Возможности решения этой задачи связаны с игнорированием нулей
матрицы
A
за счет того , что:
1) арифметитические операции с нулями не производятся ;
2) нули не обязательно хранить в машинной памяти.
§ 2. Способы хранения и представления разреженных матриц
Все способы хранения РМ заключаются в том, чтобы хранить только
ненулевые элементы матрицы или, может быть, небольшое количество нулей
вместе с ними.
2.1. Разреженный строчный формат (РСФ )
Это наиболее широко используемая форма хранения РМ . Пусть есть
прямоугольная
m
n
×
матрица
{
}
ij
aA
=
. Для ее представления в РСФ
нужно три одномерных массива:
1)
AN
– массив ненулевых элементов матрицы
A
;
2)
JA
– массив соответствующих столбцовых индексов ненулевых элемен- тов
матрицы
A
;
3)
IA
– так называемый “массив указателей ” – целочисленный массив ,
i
-я
компонента которого указывает, c какой позиции массивов
AN
и
JA
начинается описание
i
-й строки матрицы
A
. Здесь предусмотрена
дополнительная компонента , которая является последней и указывает номер
первой свободной позиции в массивах
AN
и
JA
.
-3-
§1. Введение
Строгого определения разреженной матрицы нет, но есть “нестрогие”
определения, некоторые из которых мы здесь приведем.
О п р е д е л е н и е 1.1. Разреженная матрица ( РМ) – это матрица, у
которой “много” элементов равно нулю.
О п р е д е л е н и е 1.2. Разреженная матрица – это матрица, для
которой использование алгоритмов , учитывающих наличие нулей, позволяет
добиться экономии машинного времени и памяти по сравнению с
традиционными методами.
РМ возникают при решении многих прикладных задач. Назовем некоторые
из них:
1) дискретизация уравнений математической физики – разностные схемы и
метод конечных элементов;
2) задачи линейного программирования (теория оптимизации);
3) задачи теории электрических цепей.
Основная задача курса – научиться строить эффективные алгоритмы
решения систем линейных алгебраических уравнений (СЛАУ) AU = f
( A – РМ), т.е. пытаться оптимизировать процесс решения с точки зрения
затрат машинной памяти и времени.
Возможности решения этой задачи связаны с игнорированием нулей
матрицы A за счет того, что:
1) арифметитические операции с нулями не производятся;
2) нули не обязательно хранить в машинной памяти.
§2. Способы хранения и представления разреженных матриц
Все способы хранения РМ заключаются в том, чтобы хранить только
ненулевые элементы матрицы или, может быть, небольшое количество нулей
вместе с ними.
2.1. Разреженный строчный формат (РСФ)
Это наиболее широко используемая форма хранения РМ. Пусть есть
{ }
прямоугольная n ×m матрица A = aij . Для ее представления в РСФ
нужно три одномерных массива:
1) AN – массив ненулевых элементов матрицы A ;
2) JA – массив соответствующих столбцовых индексов ненулевых элемен- тов
матрицы A ;
3) IA – так называемый “массив указателей ” – целочисленный массив, i -я
компонента которого указывает, c какой позиции массивов AN и JA
начинается описание i -й строки матрицы A . Здесь предусмотрена
дополнительная компонента , которая является последней и указывает номер
первой свободной позиции в массивах AN и JA .
