logo search
УП_САОД_2003

Матрицы с математическим описанием местоположения элементов

К данному типу матриц относятся матрицы, у которых местоположения элементов со значениями, отличными от фонового, могут быть математически описаны, то есть в их расположении есть какая-либо закономерность.

Элементы, значения которых являются фоновыми, называют нулевыми; а элементы, значения которых отличны от фонового, называют ненулевыми. Но необходимо помнить, что фоновое значение не всегда равно нулю.

Ненулевые значения хранятся, как правило, в одномерном массиве (векторе), а связь между местоположением в разреженной матрице и в новом, одномерном, описывается математически с помощью формулы, преобразующей индексы матрицы в индексы вектора.

На практике для работы с разреженной матрицей разрабатываются функции:

  1. для преобразования индексов матрицы в индекс вектора;

  2. для получения значения элемента матрицы из ее упакованного представления по двум индексам (строка, столбец);

  3. для записи значения элемента матрицы в ее упакованное представление по двум индексам.

При таком подходе обращение к элементам матрицы выполняется с помощью указанных функций. Например, пусть имеется двумерная разреженная матрица, в которой все ненулевые элементы расположены в шахматном порядке, начиная со второго элемента. Для такой матрицы формула вычисления индекса элемента в линейном представлении будет следующей:

L = ((y-1)*XM+x)/2,

где L - индекс в линейном представлении; x, y – индексы соответственно строки и столбца в двумерном представлении; XM - количество элементов в строке исходной матрицы.

        1.