Cтраница 1
Учет разреженности подразумевает исключение из вычислительного процесса операций, результат которых можно заранее предугадать. Учет пространственной разреженности обычно выполняется при операциях над матрицами, в которых преобладают нулевые элементы. Структуру матрицы можно предварительно проанализировать и в последующем итерационном вычислительном процессе не выполнять те операции, в которых одним из операндов является ноль. Учет временной разреженности выражается в пропуске вычислений по уравнениям математической модели на тех отрезках времени, на которых не происходит изменений переменных в процессе имитационного моделирования. [1]
Эффективность учета разреженности матриц проявляется и в экономии оперативной памяти, так как в алгоритмах, учитывающих разреженность, требуется хранение в памяти ЭВМ только ненулевых элементов. [2]
Выходом из положения является учет разреженности матриц в реальных задачах анализа. [3]
Собственно алгоритмы решения ЛАУ с учетом разреженности основаны на организации вложенных циклов, соответствующих стадиям исключения Гаусса или LU-разложения, но длина этих циклов определяется не размером матрицы А, а количеством ННЭ в обрабатываемых столбцах ( строках) на каждой стадии. [4]
В сочетании с неявными методами интегрирования учет разреженности матриц выливается в разработку специальных алгоритмов решения систем линейных алгебраических уравнений. Эти алгоритмы осуществляют оптимальное упорядочение строк и столбцов матрицы Якоби [32] и решение системы уравнений по методу Гаусса, при этом минимизируется количество появляющихся при решении новых ненулевых элементов, а действия производятся только над ненулевыми элементами матрицы. Такие алгоритмы применены, например, в программе ПАУМ, где разреженность матриц учитывается в рамках метода узловых потенциалов. В обоих случаях затраты машинной памяти и число арифметических операций при решении системы алгебраических уравнений пропорциональны первой степени показателя сложности схемы, что позволяет анализировать с помощью неявных методов сложные схемы. [5]
Алгоритмы метода прогонки в отличие от более общих алгоритмов учета разреженности матриц с нерегулярной структурой характеризуются большей простотой программной реализации. [6]
Методом разреженных матриц называют метод решения СЛАУ на основе метода Гаусса с учетом разреженности ( первичной и вторичной) матрицы коэффициентов. [7]
Наибольшие трудности возникают при разработке алгоритмов решения систем уравнений (3.19) - (3.21) с учетом разреженности матриц Аг, Аг и As. Чаще всего эту проблему решают путем упрощения не процедур оперирования с матрицами Аг, Аг и As, а упрощения самой структуры этих матриц. Так как структура этих матриц связана с конфигурацией эквивалентной схемы, то упрощение в них может быть достигнуто путем введения некоторых дополнительных ветвей в эквивалентную схему. При этом матрицы Ап АГ и AS могут быть превращены в нулевые или диагональные. Тогда или вообще отпадает необходимость решения каких-либо систем алгебраических уравнений, или каждая из этих систем превращается в несколько несвязанных между собой отдельных уравнений, разрешение которых относительно искомых величин не представляет трудностей. [8]
Таким образом, диакоптические методы анализа обеспечивают ускоренное решение систем ОДУ большой размерности благодаря учету блочной разреженности матриц Якоби таких систем и возможности организации автономных вычислительных процессов для подсистем. Это позволяет проводить анализ сложных объектов при ограниченном объеме ОП ЭВМ, а также выполнять параллельные вычисления в многопроцессорных ВС. [9]
Для решения малых задач ( десятки и сотни уравнений) обычно используют стандартные программы, реализующие прямые методы, для решения больших задач ( тысячи уравнений) можно использовать прямые методы с организацией эффективного обмена между оперативной и внешней памятью ЭВМ или с учетом разреженности обрабатываемых матриц. Для решения уникальных задач ( десятки тысяч уравнений) целесообразно применять итерационные методы. [10]
Характерным примером учета разреженности матриц является метод сканирования М - матрицы, в котором вместо матричных выражений (1.24) и (1.25) при компиляции объективных программ используются развернутые выражения производных переменных состояния. При этом исключаются такие арифметические действия, результат которых равен либо нулю, либо одному из операндов с возможной переменой знака. Исследования показали, что число арифметических операций, выполняемых на одном шаге интегрирования, сокращается на один-два порядка даже при анализе схем умеренной сложности. Использование метода сканирования М - матрицы в программе ПАШ [31] позволило при минимальных требованиях к емкости оперативной памяти анализировать схемы, включающие до 50 транзисторов. [11]
В то же время для учета разреженности матрицы более выгодной оказывается узловая форма записи системы уравнений, поскольку для сложных систем заполненность нулями у матрицы Максвелла меньше, чем у матрицы Кирхгофа. Кроме того, структура матрицы Максвелла совпадает со структурой схемы цепи и не зависит от выбора контуров, что упрощает логику алгоритмов упорядочения исключения переменных. [12]
Имеются значительные резервы в повышении эффективности неявных методов. Эти резервы связаны с возможностью учета разреженности матрицы Якоби системы (4.16) и реализуются в методе организации вычислений, называемом методом разреженных матриц. Суть этого метода заключается в том, что в памяти ЦВМ хранятся только ненулевые элементы матрицы Якоби, а при решении системы (4.16) методом исключений по Гауссу производятся арифметические операции по пересчету только тех коэффициентов, значения которых изменяются. Рациональность такой процедуры очевидна, но ее алгоритмы сложны из-за необходимости выделения изменяющихся коэффициентов из множества всех коэффициентов. [13]
Вычисление матрицы Якоби как матричного произведения AYA без учета разреженности матриц А и Y нерационально, так как приводит к излишне большим затратам машинных времени и памяти. В то же время статистические исследования показывают, что ненулевыми в этих матрицах оказываются лишь около 240 элементов. [14]
Первая в мировой литературе книга, специально посвященная разреженным матрицам, - матрицам с большим числом нулевых элементов. В ней в доступной форме излагается техника применения разреженных матриц в широких классах задач, использующих вычислительные методы, линейной алгебры и математического - программирования. Учет разреженности матриц позволяет экономить, время решения на электронных вычислительных машинах, увеличить размерность задач. [15]