Введение

Матрица, в которой ненулевые элементы расположены только в диагональной полосе. В математике, в частности в теории матриц, матрица с полосой (или полосовая матрица) — это разреженная матрица, ненулевые элементы которой сосредоточены в диагональной полосе, включающей главную диагональ и ноль или более диагоналей с каждой стороны.

Пропускная способность

Формально, рассмотрим матрицу n×n, A=(ai,j). Если все элементы матрицы равны нулю вне диагонально-ограниченной полосы, диапазон которой определяется константами k1 и k2:

то величины k1 и k2 называются нижней полосой и верхней полосой соответственно. Полоса пропускания матрицы – это максимум из k1 и k2; другими словами, это число k, такое что если .

Приложения

В численном анализе матрицы, возникающие при решении задач конечных элементов или конечных разностей, часто являются полосными. Такие матрицы можно интерпретировать как описание связи между переменными задачи; полосность соответствует тому, что переменные не связаны на произвольно больших расстояниях. Эти матрицы можно классифицировать далее, например, существуют полосные матрицы, в которых все элементы в полосе ненулевые. Задачи в более высоких размерностях также приводят к полосным матрицам, при этом сама полоса, как правило, оказывается разреженной. Например, решение частного дифференциального уравнения на квадратной области (с использованием центральных разностей) даст матрицу с шириной полосы, равной квадратному корню из размерности матрицы, но внутри полосы ненулевыми будут только 5 диагоналей. К сожалению, применение метода Гаусса (или, эквивалентно, LU-разложения) к такой матрице приводит к заполнению полосы большим количеством ненулевых элементов.

Форма полосы из редких матриц

С точки зрения вычислений, работа с матрицами с полосами всегда предпочтительнее работы с квадратными матрицами аналогичных размеров. Матрицу с полосами по сложности можно сравнить с прямоугольной матрицей, у которой число строк равно ширине полосы исходной матрицы. Таким образом, объем работы при выполнении операций, таких как умножение, существенно снижается, что часто приводит к значительной экономии времени и вычислительной сложности. Поскольку разреженные матрицы позволяют выполнять вычисления более эффективно, чем плотные, а также более эффективно использовать компьютерную память, было проведено множество исследований, направленных на поиск способов минимизации ширины полосы (или непосредственного уменьшения заполнения) путем применения перестановок к матрице или других подобных преобразований эквивалентности или подобия. Алгоритм Кутилла-Макки можно использовать для уменьшения ширины полосы разреженной симметричной матрицы. Однако существуют матрицы, для которых более эффективен обратный алгоритм Кутилла-Макки. Существует множество других методов. Задача нахождения представления матрицы с минимальной шириной полосы посредством перестановок строк и столбцов является NP-трудной.