Cтраница 2
Система ЛАУ (1.48) решается на каждой итерации относительно АХЙ, а затем вычисляется h i Xй - f - AXh. Решение системы (1.48) - наиболее трудоемкий этап в реализации метода Ньютона, определяющий его вычислительную эффективность на каждой итерации. Практически метод Ньютона применим лишь при учете разреженности матрицы Я в ходе решения систем ЛАУ большой размерности. [16]
ЭВМ; N - показатель сложности анализируемого объекта; Я, Ш - число ньютоновских итераций на одном шаге и шагов интегрирования; ае [1, 3] и зависит от свойств выбранного алгоритма решения системы линейных алгебраических уравнений ( ЛАУ) на каждой ньютоновской итерации. Если разреженность матрицы Якоби не учитывается, то а3 и возможности применения неявных методов ограничиваются задачами сравнительно малой размерности. Поэтому в САПР сложных объектов ( таких, как БИС) необходим учет разреженности матриц. При этом а в (5.15) оказывается в интервале [1, 2] и существенно повышает эффективность неявных методов. [17]
Проблемы повышения эффективности математического обеспечения для процедур анализа стоят не менее остро, чем для процедур синтеза. Большие размерности математических моделей, необходимость выполнения многих вариантов анализа этих моделей в маршрутах проектирования выдвигают в число наиболее актуальных проблему снижения вычислительных затрат. Эта проблема решается в следующих основных направлениях: диа-коптика - исследование сложных систем по частям, основная идея диакоптики - снижение вычислительных затрат за счет замены одной сложной задачи совокупностью задач малой размерности; адаптируемость - автоматический выбор математических моделей и методов, оптимальных но показателям эффективности, применительно к особенностям конкретной задачи; учет пространственной и временной разреженности. [18]
Учет разреженности подразумевает исключение из вычислительного процесса операций, результат которых можно заранее предугадать. Учет пространственной разреженности обычно выполняется при операциях над матрицами, в которых преобладают нулевые элементы. Структуру матрицы можно предварительно проанализировать и в последующем итерационном вычислительном процессе не выполнять те операции, в которых одним из операндов является ноль. Учет временной разреженности выражается в пропуске вычислений по уравнениям математической модели на тех отрезках времени, на которых не происходит изменений переменных в процессе имитационного моделирования. [19]
Экономичность метода решения систем АУ определяется также затратами оперативной памяти. При неучете разреженности только на хранение матрицы Якоби нужно / гг ячеек памяти. Поэтому если для одного слова используется 8 байт, то при п 100 для хранения требуется 80 кбайт, а при п 500 - уже 2 Мбайт. Итак, подтверждается вывод о необходимости учета разреженности при решении задач с пппр, где Пщ зависит от характеристик используемой ЭВМ и, как правило, составляет несколько десятков. В задачах анализа распределенных моделей, в которых п может превышать 104, экономичность метода по затратам машинной памяти становится одной из важнейших характеристик. В таких случаях применяют либо релаксационные методы, либо метод Ньютона с использованием на каждой итерации метода Гаусса, но в рамках рассматриваемого ниже диакоптического подхода. [20]
Быстродействие во многом зависит от выбора алгоритмов моделирования. Проблема обеспечения требуемого быстродействия имеет ряд аспектов: Схема содержит большое число элементов, поэтому матрица коэффициентов, имеющая размерность WM N, где N - число элементов схемы, очень большая. Вместе с тем элементы схемы соединены с небольшим числом других элементов, и поэтому матрицы коэффициентов в основном заполнены нулями. Разреженность матриц может быть учтена специальными алгоритмами. Такие алгоритмы рассмотрены в, [ 9.3, 9.41 и основаны на определенной упорядоченности последовательности вычислений с учетом разреженности матриц. Другой аспект этой проблемы связан с выбором шага интегрирования и числа шагов при расчете переходных процессов. Особенно сложен расчет при моделировании нелинейных высокочастотных схем, где одновременно необходимо рассматривать, и высокочастотное заполнение, и огибающую. Первое требует малого шага интегрирования, а второе - длительного наблюдения. Здесь необходима отработка алгоритмов, построенных с использованием экстраполяции данных. Учитывая, что программы должны быть универсальными, решить эту задачу довольно сложно. [21]
Следует различать исходную и итоговую разреженность матрицы. Исходная разреженность определяется числом ненулевых элементов, имеющихся в матрице до начала выполнения исключений неизвестных по методу Гаусса. Такие нулевые элементы называют первичными. Однако в процессе вычислений по (5.4) некоторые коэффициенты ctij, бывшие нулевыми, могут стать ненулевыми. Такие коэффициенты называют вторичными ненулевыми элементами. Итоговая разреженность определяется суммарным числом первичных и вторичных ненулевых элементов, и эффективность учета разреженности матрицы тем выше, чем больше итоговая разреженность. [22]
Преимущества метода сканирования М - матрицы вытекают из следующего обстоятельства. Топологические и компонентные матрицы электронных схем являются сильно разреженными. Но в этом случае можно вообще отказаться от выполнения операций умножения при вычислении, например, векторов Us, U л, VL по (3.13) - (3.15), так как результат умножения известен заранее: это либо нуль, либо один из операндов, возможно с измененным знаком. Компонентные матрицы и матрицы коэффициентов разветвления являются разреженными еще в большей степени, чем М - матрица, так как это диагональные матрицы. Учет разреженности приводит и к резкому сокращению затрат машинной памяти, поскольку не нужно хранить в памяти машины нулевые элементы матриц, а сведения о структуре М - матрицы можно представить в компактной форме. [23]
Анализ статических режимов сводится к решению систем АУ. Для решения АУ применяют итерационные методы, основные характеристики которых - сходимость и скорость сходимости к точному решению. В САПР применяют в основном методы простой итерации, Ньютона и релаксационные. Методы простой итерации и релаксационные имеют линейную скорость сходимости и требуют небольших вычислительных затрат на одну итерацию. Эти методы применяются в основном для решения систем АУ большой размерности. Метод Ньютона имеет квадратичную скорость сходимости, но в общем случае сходится только в окрестности точного решения. Для расширения области сходимости метода Ньютона применяются метод продолжения решения по параметру и метод дифференцирования по параметру. Метод Ньютона и его модификации сводятся к решению систем ЛАУ на каждой итерации. Для решения систем ЛАУ наиболее широко применяют метод Гаусса и LU-разложения. Для систем ЛАУ большой размерности эти методы эффективны только при учете разреженности матриц коэффициентов. [24]