Методы, использующие алгебру разреженных матриц

Возможность снижения вычислительных затрат при расчете больших схем вытекает из того, что в уравнении (3.70) большинство элементов равно нулю. Здесь матрица A эквивалентна одной из матриц схемы (матрице узловых проводимостей Y, контурных сопротивлений Z или др.), в зависимости от используемого в алгоритме метода составления уравнений схемы. Оценим коэффициент заполнения К_З на примере матрицы узловых проводимостей Y. Подсчитано, что количество ненулевых элементов в в любой i -й строке матрицы Y лежит в пределах , в то время как полное количество элементов в строке равно числу узлов в схеме без одного (заземленного), т.е. . Таким образом, среднее значение коэффициента заполнения может быть найдено, как . Отсюда нетрудно рассчитать К_З для схем различной сложности. Так для схем с числом узлов (низкий уровень интеграции) , для схем с числом узлов (средний уровень интеграции) , с числом узлов (БИС) . Отсюда вытекает возможность значительной экономии памяти путем записи матрицы Y не в виде двумерного массива, занимающего ячеек, а в виде одномерных массивов, записанных в определенном порядке.

Хранение разреженной матрицы в памяти ЭВМ должно обеспечивать: 1) экономию памяти и числа операций, необходимых для преобразования матрицы в процессе решения системы линейных уравнений; 2) простоту доступа к любому элементу матрицы при формировании системы; 3)учитывать возможность появления новых ненулевых элементов в матрице.

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

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

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

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

произведение .

Обычно после прямого хода преобразованная матрица оказывается почти полностью заполненной. В связи с этим большое значение приобретает последовательность исключения неизвестных, от которой зависит количество новых ненулевых элементов. Правила выбора порядка исключения неизвестных, обеспечивающие минимальное число новых нулевых элементов, получили название критерия оптимальной нумерации. Из большого количества предложенных в литературе критериев, можно отметить критерий Марковица, в соответствии с которым для очередного исключения выбирается та неизвестная, координаты которой (i,j) удовлетворяют условию:

,

где и – число ненулевых элементов в строке i и столбце j.

Величина M равна максимальному числу новых ненулевых элементов, которые могут появиться в результате исключения неизвестного с координатами (i,j). Более эффективный критерий предложили Сато и Тинней применительно к методу LU-разложения. Он основан на том, что количество ненулевых элементов в пересчитанной оставшейся части матрицы на каждом шаге LU-разложения зависит от того, какая пара столбец-строка была выбрана на предыдущем шаге разложения. Очевидно, что нужно выбирать те пары, при разложении по которым образуется минимальное количество новых ненулевых элементов. Из формулы (3.22)

видно, что на месте нулевого элемента появится ненулевой элемент в том случае, если одновременно и . Отсюда следует, что для минимизации числа новых ненулевых элементов на каждом шаге для разложения нужно выбирать ту пару столбец-строка, в которой минимальное число ненулевых произведений . Выбрав по этому правилу последовательность рассмотрения пар столбец-строка, нужно пронумеровать узлы схемы с этой последовательностью и сформировать матрицу A для новых номеров. Следует отметить, что нередко после очередного шага разложения возникает ситуация неопределенности, когда несколько пар столбец-строка дают одинаковое число новых ненулевых элементов. В этом случае выбирается та пара, в которой общее число ненулевых элементов максимально, так как при этом из дальнейшего рассмотрения исключается максимальное число ненулевых элементов.

В целом методы оптимальной нумерации позволяют значительно снизить затраты памяти и времени на расчет схем с разреженными матрицами. Например, при расчете 100-узловой схемы применение оптимальной нумерации узлов ускоряет расчет почти в 40 раз. Принято считать, что затраты времени на решение системы линейных алгебраических уравнений определяются количеством длинных операций – умножения и деления, которое не может быть меньше , где N – порядок системы. Затраты памяти при этом пропорциональны . Опыт свидетельствует, что при использовании алгоритма оптимальной нумерации затраты памяти и времени почти пропорциональны N.

Дата добавления: 2014-10-15