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

V» . I

РОССИЙСКАЯ АКАДЕМИЯ НАУК САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ ИНФОРМАТИКИ И. АВТОМАТИЗАЦИИ

ПРОБЛЕМЫ РЕАЛИЗАЦИИ И ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ЧИСЛЕННО-АНАЛИТИЧЕСКИХ МЕТОДОВ ДЛЯ СХЕМОТЕХНИЧЕСКОГО МОДЕЛИРОВАНИИ

Специальность: 05.13.16 - Применение вычислительной техника, математических методов и математического моделирования в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

На прэЕзх рукописи

У СУЩЗД

Работа выполнена е .Институте автоматизации, проектирования Российской Академии Наук.

Научный руководитель: • доктор физико-математических наук, старший научный сотрудник МИХАИЛОВ Владимир Борисович

Официальные оппоненты: доктор физико-математических наук, профессор, академик АИН РФ НЕФЕДОВ Евгений Иванович кандидат физико-математических наук..

Воробьев Владимир Иванович

Ведущая организация - Санкт-Петербургский электротехнически! университет.

заседании специализированного совета Д 003.62.01 Санкт-Петербургского института информатики и автоматизации Российской А» по адрес! 199178, Санкт-Петербург, В.О., 14 линия, д. 39.

С диссертацией можно ознакомиться в библиотеке института.

Защита состоится

1993 г. в

часов нг

Автореферат разослан

Ученый секретарь специализированного совета кандидат технических наук

В.Е.Марлей

I: ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность теш диссертации.

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

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

Численные эксперименты показывают, что математические модели полупроводниковых субмикронных СВЧ-микросхем обладают рядом ноеых уникальных сеойств, ранее не имеющих аналогов. К таким новым свойствам относится феномен сверхжесткости их систем агебро-дифферэнци-альных уравнений, который заключается не только в высоком значении коэффициента жесткости (10б...1012), но и в невозможности выделить мягкую и жесткую компоненты спектра собственных колебаний, т.е. е невозможности разделить спектр на изолированные группы колебаний, параметры которых можнб~~класифкцировзть как быстрые и медленные.

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

Предложенная В. Б. Михе!*"-*" рмула резольвенты регулярного пу-

г!

чка, представленная через скелетные произведения собственных Еекто-ров, возможность выделения алгебраической части решения е алгебро-дифференциальных системах позволили создать ноше численно-аналитические метода, решение в которых декомпозировано по составляй®» спектра собственных колебаний. Применение обратных преобразовали! Лапласа дает возможность получить решение и ее первую производную I аналитическом виде. Реализация этих идей показала, что данный класс численно-аналитических методов существенно, превосходит численные метода решения жестких систем как по точности вычислений, так и пс быстродействию. Применение метода Л.В.Канторовича принципиально позволяет полутать и асимптотически близкое решение для нелинейнш рлгебро-дифференциальных систем (ОДУ) на ограниченном интервале с последующим сшиванием решений известным методом припасошвания. '

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

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

В связи с изложенным, тематика исследований в диссертационной работе, направленная на минимизацию ресурсов при реализации числен-но-аналитическогс подхода, предсталяется актуальной и практически значимой при создании программного обеспечения САПР РЭА.

Целью работы является:

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

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

- исследование ЕСЗЛ^^КНОСТЭ^ ПОЕКШ^НЛЯ Э'^ф^ктнвкости 1ГСОГРЗ\*МКОГО

з.

- разработка ускоренных мэтодое построения семейств частотных характеристик в многовариантном анализе.

Методы исследования. При выполнении работы в качестве математического аппарата исследований использовалась теория дифференциальных уравнений, теория матриц, численные методы, теория цепей, методы расчета электронных схем для залчч САПР.

Научная новизна работы. Научная новизна работы определяется следующими, защищаемыми положениям!:

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

- выполнено исследование комбинированного интерполяционного алгоритма (на основе методов Ньютона, ЧебышеЕа и Мюллера), разработана стратегия и критерии переключения методов, что позволило на порядок ускорить 'алгоритмы анализа, устойчивости радиоэлектронных схем;

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

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

- сформулирована и доказана теорема о модификации матрицы, обратной параметрически зависимой ^-матрице, если та представляется в виде суммы параметрически зависимой одноранговой матрицы и регулярной параметрически независимой Л-матрицы; на основе данной теоремы

предложен новый алгоритм построения семейств частотных характеристик в пространстве варьируемых параметров, вычислительные затрат! для нэго на 1-2 порядка ниже, чем в известных методах многовариантного частотного анализа.

Практическая значимость работы.

В работе выполнен цикл важных исследований по применению интерполяционных алгоритмов для решения обобщенной проблемы собственны: значений пучков разреженных матриц в технических приложениях, эта исследования позволили создать более эффективное программное обеспечение для численно-аналитических методов моделирования аналоговые радиоэлектронных схем. Показаны дальнейшие резервы улучшения характеристик программ и построения новых алгоритмов при использованш особенностей строения матриц электронных схем;. это позволило получить более эффективные программы, для выполнения многовариантных расчетов (в перспективе - для оптимизационных задач). Бее предложенные е работе алгоритмы позволяют шап^.шзировать затраты оператиЕНо£ памяти персональных ЭВМ, что повышает возможности программного обеспечения САПР для численно-аналитических методов (увеличение степени интеграции моделируемых схем). -

Реализация и Енедрение результатов работы.

По разработанным в диссертации алгоритмам реализована часть нового программного обеспечения пакета схемотехнического моделирования и оптимизации аналоговых'радиоэлектронных схем "СПЕКТР", разрабатываемого в ФИАЛ РАН е период 1939-1992 г.г. Некоторые алгоритмь переданы, для реализации программного обеспечения в САПР полупроводниковых СВЧ-микросхем . на основе арсенида галлия, разрабатывемой I НИИ радиоаппаратуры (г. Санкт-Петербург).

Апробация научных результатов."

Результаты научных исследований докладывались на конференшп "Проблемы нелинейной электротехники" (Киев, 1992 г., ИШЭ' АН Украины); на конференции "Проблемы автоматизированного моделирования I электронике" (Киев, 1993 г.), нз семинарах в филиале МАП РАН.

по т6м9 ии^сэртещш с л v" 5 л» хн о е чны тшт стзтыт и т93исы ттз^х док-

падав на научных конференциях.

Структура и объем работы. Диссертация содержит 173 страницы текста и иллюстраций и состоят кз введения, четырех глав, заключения, библиографического списка литературы (139 наименований), 4 таблиц и 8 рисунков.

II. КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ.

Е первой главе диссертации приведен обзор наиболее значимых результатов для численно-аналитических методов решения линейных алге-бро-дифференциальных систем произвольного индекса, тлеющих в сисей численной основе спектральные разложения регулярных пучков матриц. Показано, что наибольшей эффективности эти методы достигают, когда компонентные матрицы Zk. представимы в виде скелетных произведений собственных векторов' или векторов жорданоЕЫХ цепочек.

Во многих технических приложениях, в том числе для электронных схем, математические модели объектов моделирования в виде вырожденных ОДУ- составляются из моделей структурных элементов, входящих в общую систему уравнений. В наиболее частых случаях в общую систему нелинейных алгебро-дифференцкзлышх уравнений входят только часть компонент вектора искомых переменных x(t) и его производных x(t), тогда будем 'иметь вырожденную систему

î(xb,xa,t) =0П , (1)

где хь и х - подмножества переменных х = (х1,...,хп)т и их производных, для которых выполняются условия X = XbU X , ХЬП Ха / 0.

Подмножества хь и х - это компоненты x(t) и x(t), которые входят соответственно в дифференциальную и алгебраическую части вырожденной системы (1 К

В моделировании широко используются также линейные алгебро-диф-ференциальные системы уравнений (ЛАДСУ), которые либо описывют самостоятельные классы моделируемых объектов (Л1шейные схемы и системы), либо служат для качественного и количественного изучения нелинейных систем (1). ЛАДСУ могут иметь как зависящие от времени пэры матриц (B(t),A(t)), так и постоянные (В,А). В приложениях наиболее

часто встречаются вырожденные системы

B(t) x(t) = A(t) x(t) + f<t), x(0) = Xq

В X(t) = A X(t) + f(t), X(0) = Xq

(2, (з;

где x0 - вектор начальных условий (е точке t=0) порядка, п; матрицы при производных В(t) и В вырождены (при этом одновременно могут быть вырождены и матрицы A(t) и А, но системы (2) и (3) совместны и пучки матриц D(\,t)=\B(t)-A(t) и Б(\)=\В-А регулярны.

В частности, матрицы B(t) и A(t) могут быть получены при линеаризации системы (1), т.е.

а .

— F(x, X, t) = В(х, х, t) = B(t) дх

д

— F(x, х, t) = - А(х, x, t) = - A(t). dx

В анализе электронных схем системы (3) образуются при линеаризации (1) в статическом режиме и используются для анализа устойчивости, расчета частотных характеристик и шумов, построения переходных и установившихся процессов в режиме малого сигнала (линейный реким). Уравнения нелинейных элементов линеаризуются в рабочих точках и они замещаются эквивалентной схемой с постоянными, элементами', а затем формируется система (3) с постоянными вещественными сильно разреженными матрицами коэффициентов.

Регуляршй пучок БШ= ЛВ-А, для которого ранг матрицы В меньше степени характеристического полинома rank В < deg[d.et(/\B-A)3 с помощью преобразований с некоторыми постоянными невырожденными матрицами Р и Q может быть приведен к строго-эквивалентному канони-ноническому квазидиагональному виду

Р(/\В - A)Q =

A.I-J

4f?

(4)

где J - жорданова структура, определяемая конечны?,® элементарными делителями пучка, s Jœ - бесконечными.

Каноническая форма (4) определяет структуру решений ЛАЛСУ произвольного индекса.

т.

Рассмотрен алгоритм приведения регулярного пучка к канонической форме, идейно близкий к алгоритму А.Н.Малышева для дихотомии спектра. Показано, что алгоритмы такого типа нецелесообразно применять в программах моделирования электронных схем из-за большого потребления ресурсов (объем вычислений и затраты оперативней памяти).

Анана логический вид решения ЛАДСУ (3) индекса г при наличии нелинейных элементарных делителей в спектре коночных собственных значений пучка может быть представлен в форме

ШГ V г -И Mt-т)

Z^ t е k В х0 + j(t-T) е Л Г(т)йт

Ш 0-1}

г Qq f(t) + Q, f :(t) + ..... + QI>_1 f (t), (5)

где a - количество жордановых клеток в жордановой структуре J из (4) для конечных элементарных делителей; mk (k=1,...,s) - величина k-го жорданоЕа ящика в структуре J; ■ - .матричный компонент, соответствующий k-му блоку для собственного .значения A.k (J=1.....m^);

Q0 ,..., Qr_1 - постоянные вещественные матрицы; f(t) и i^m'(t) -вектор входных воздействий и его ш-я производная (ш=1....,г-1).

Если rank В = degtdetCVB-A)], т.е. ранг матрицы при производных совпадает со степенью •характеристического полинома пучка, то такие ЛАДСУ имеют единичный индекс (системы типа "ранг-степень"), а в решении i(5) все матрицы Q1 ,...., Qx,_1 - тождественно нулевые.

В задачах моделирования современной'радиоэлектронной аппаратуры наибольший интерес представляет случай различных собственных значений, т.к. вероятность возникновения лгратннх в активных схемах практически равна нулю. Компонентные магргтн в (5) могут быть представлены в виде сумм скелетных-лреизведеягёй векторов из.правой и левой жорджешых цепочек <Б.Б.®йшйлов), а в интересующем нас простейшем случае в виде скелетных произведений собственжк. векторов, т.е.

zil " ui

Для систем едйничнего индекса теперь будем иметь

m

x(t) = ^ _utrj

t

+ Qq i(t). (q

r . Ä.« (t—X)

e 1 В x0 + e 1 f(t)dx О

В главе показано, что данный вид решения (В.Б.Михайлов, 1984),

будет особенно эффективен, если f(t) - сложная? вектор-функция, ко торую можно представить е Еиде

, - пБ

I(t) = У Aj <p-j(t), (7

где А^ - вещественный постоянный вектор амплитуд; cp_j (t) - элементарная скалярная функция времени, имеющая изображение по Лапласу ns - количество элементарных функций в f(t)'. Обозначим

t .

г V.(t-T)

е1 (p^(t)dT = ф-^t), (8

J U -чг

о

где <|>.y(t) - аналитическая функция (интеграл Коши) для и <pj(t) Поскольку матрицу Q0 е (6) можно представить как

(аВ-А)"

т

ui ч

(9

(а - нэкоторая вещественная константа, для которой постоянная вещественная матрица С - аБ-А не выровдена), а также перед вычислениями 'x(t) предварительно накопить скалярные произведения вида

-1

(В х0) = а±; vi А^ = P1;j; 7i= ~ а)

(10)

то с учетом (Т--10) может получена оптимальная по объему вычислений формула ддя численно-аналитического вида решения ЛАДСУ, т.е.

щ 1=1

c^e 1 +

Jil

1=1

f,il(t) +

+ y(t), (11)

где y(t) получается из решения линейной алгебраической системы с сильно разреженной вещественной матрицей С = аВ-А -и вектором (7)

(аБ-А) у(t) = f(t).

Поскольку матрицу также можно предварительно привести к левому греугольному виду с помоаью Ш-рэзложения и для кагщого t=tk век-

то him для каждой точки t=t}.

и у---;

\Г f t ГТ.-\ ^гт- "1

1

надо будет решить промежуточную систему с разреженной матрицей Ь и умножить полученный вектор сгграЕа на разреженную матрицу М в фак-торизоЕанной форме. С учетом этого объем вычислений для (11) получается минимальным я не требуется хранение плотной матрицы. 0о, что сокращает время счета на 20% и затраты памяти на п1- двойных вещественных чисел- (по сравнения с реализацией с пакете "СПЕКТР", где матрица 0о вычислялась по формуле (9) и была размещена построчно во Енешней памяти).

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

Эффективная реализация (11) особенно важна в нелинейном анализе схем в численно-аналитической модификации (В.Б.Михайлов, 1987) метода Л.В.Канторовича для вырожденных систем, когда невязка для к-го аналитического приближения х^Ш

1(1с)а) Ха(к), г) 02)

аппроксимируется, подходящим набором базисных функций в виде (7). и затем находится аналитическая поправка к решению из системы (3) щи. Ш) =. - ?(к)(+")..

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

Во второй главе диссертации рассмотрены возможности применения СШ-алгоритма для решения обобщенной проблемы собственных значений регулярного пучка разреженных матриц и приведены основные характеристики возможных реализаций алгоримтов. Признано более целесообразным использовать интерполяционные методы. В главе предложен новый алгоритм, позволяющий привести регулярный пучок к блочно-дизгсналь-ному еиду, в котором один кз блоков не зависит от л, з для второго можно решать обычную проблему собственных значений ¿зит-МЬ-О, е . гй которой вещественная ыатипиз Т является тъеххлэгснллыюЯ с про-

£ым окаймляющим столбцом и имеет порядок m = гапк В, т.е.

Т =

Т11t12

* t t "21 l22 23

t32t33t34

t

1ro 3m

(12)

• t t ja-1 ,m-1 m-1 ,m

■ t t . m,m-1 шт

При этом максимально используются разреженные свойства исходного пучка матриц D(Á.) =ХВ-А и особое Енимание уделено минимизации объема вычислений, затрат оперативной памяти, числа обменов с внешней памятью, устойчивости процесса к ошибкам вычислений.

Показано, что применение формы (12) позволяет существенно минимизировать объем вычислений при использовании интерполяционных методов, если в качестве соответствующей функции использовать детер-минантнув det(T - XI )= 0. Предложен алгоритм вычисления определителя постоянной матрицы С = Т - X*I (X* - приближение к корню) нэ требующих специальных-затрат оперативной памяти (дополнительно четыре комплекссных числа), не портящий матрицу Т, объем вычислений для которого составляет только -Зш операций в полукомплексной или вещественной арифметике. Рассмотрен также -и известный способ вычислений определителя такой матрицы и обсуждена -проблема его неустойчивости к вычислительным ошибкам.для СЕерхжестких систем.

В третьей главе работы'выполнен цикл исследований . интерполяционных методов и предложен комбинированный интерполяционный алгоритм на основе разностных аналогов методов Ньютона, Чэбышева и Мюллера..

Исследования метода Мюллера показали, что он имеет тенденцию перехода в комплексную арифметику даже при хороших приближениях к вещественному корню, что существенно увеличивает Бремя расчетов.

Исходя из этого, предложена оптимальная стратегия, для которой несколько начальных шагов итерационного процесса для каждого корня выполняются только методами Ньютона и ЧебышеЕа, а включение' в итерационный рроцесс метода Мюллера (для получения комплексно-сопряженных пар корней) производится только при выполнении некоторого критерия. Предложенная модификация позволила почти на порядок сократить время анализа устойчивости- В ¡главе исследовался также вопрос

оценки точности вычисления корней и сходимости процесса в зависимости от точности вычисления значений детерминантной функции в окрестности корня. Показано, что если определитель даже при очень близком приближении к значении корня вычисляется с точностью не хуже 10 процентов, то на каждой последующей итерации можно утешить хотя бы один десятичный знак (такая ситуация возникает, когда приближение содержит уже 8..-.10 правильных значащее цифр при 16-разрядной мантиссе., Предложен новый алгоритм вычисления кратности корней,- основанный на свойствах логарифма детерминантной функции. Алгоритм позволил существенно сократить объем вычислений, а итерационный процесс теперь можно выполнять только для первого из кратных корней.

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

Исследовался также пучковый вариант метода обратной итерации.

Четвертая глэеэ диссертации посвящена проблеме минимизации вычислительных ресурсов при решении многоваризнтных задач анализа линейных схем в частотной области.

Исследование свойств элеу-знтарных. матриц элементов в расширенном однородном координатном базисе (РОКБ) показало, что они могут быть представлены в виде суш скелетных произведений постоянных векторов строго фиксированной структуры с ненулевыми элементами, равным;! 1 или -1, причем только при одном из слагавши; выделен скалярный множитель, являющийся параметром (номиналом) элемента.*Эти свойства позволили сформулировать простой алгоритм выполнения преобразований подобия для пучков матриц электронных схем, позволяющих выделить матрицу для явного вида (13) в алгебраической части решения ЛАДСУ единичного индекса. Матрицу 0.0 в (б) моГ'-'о такзге (В.Б.Михзй-" лов, 1987) представить в виде

-■о : 2 ;

о а";

1 -

с:

о

где Р1 и Р£ - неособенные вещественные квадратные матрицы порядка. п, приводящие регулярный пучок АБ-А к виду ,

PlBP2

J11 О

и Р.,А Р2 =

А А 11 Й12

а23 а22

где det В^^О и det А^тЮ, а матрицы В^ и А^2- невырожденные квадратные блоки порядков m и п-га соответственно (m = rank В).

Исследования одноранговых' представлений матриц моделей элементов электронных схем позволили предложить новую модификацию известного эффективного алгоритма выделения блока А20 (В.Б.Михайлов и 'Г.В.Мазюкевич, 1987), не требующую каких-либо арифметических операций для вычисления матричных коэффициентов.

Предложена также новая модификация базиса переменных для РОКБ, которая Еыделяет систему линейнонезаЕисимых индуктивных токов, поникает общий порядок системы уравнений и исключает преобразования подобия для индуктивной части матрицы при производных, что также упрощает задачу выделения алгебраической части решения;

Предложено обобщение метода модификации обратной матрицы, часто используемого в различных прикладных задачах. Если для даух вейто-векторов и и v и невырожденной матрицы А выполняется соотношение vT А-1 и ф -1, то формула модификации тлеет вид

[а + u yt]

-1.

А

A~1u ут А '

1 + vT.A_1u

В диссертации предлагается обобщение этого соотношения для регулярных \-матриц. Если зависящая от параметра £ регулярная А.-мат-трица д(к, О имеет вид

Da, и = D0(M + six, £) u vT,

(В0(Л) - регулярная ^-матрица, не зависящая от g(X, £) J скалярная функция от аргументов £ и X; и и v - векторы), то имеет место соотношение

ва, Е) 1 = D0a) 1 - ga, v —0--s-2—zr- <14>

0 ° j + ga, 5) у D0a) ы

На опнова данной формулы предложен новый быстродействующий ал-

горитм построения семейств частотных характеристик. Минимизация, вычислительных ресурсов достигатся предварительной подготовкой, включающей в себя:

- однократное разложение матрицы схемы для каждой частотной точки и получение вектора решения при номинальных значениях;

- однократное решение системы с уже разложенной матрицей для каждого параметра с известным для него фиксированным вектором и вычисление двух констант.

Алгоритм основан на свойстве изменяемой части матрицы элемента 'быть представленной в'виде- и V1, где иит - векторы.

Рассмотрим алгоритм многовариантного расчета по- шагам: Шаг 1. Для круговой частоты со = формируем постоянную матрицу

при 5 = £0, т.е. В(Зшк>Е0) = 3(^В(Е0) - Ш0)-

Шаг 2. Осуществляем Ш-разложение постоянной комплексной матрицы

= Ь

•т

Шаг 3. Решаем систему уравнений Еида Ь М Х(;)и,к,?0) = Р.

Шаг 4. .Для варьируемого параметра для которого нам известны

Еекторы и и • V из скелетного разложения матрицы элемента, решаем

систему вида Ь Мт г = и, определив тем самым ъ =

Шаг 5. Вычисляем скалярные произведения вида

7Т г = 7Т [ ] = а и 7Т = р

с ранее полученными векторами ' z и Х(.

Шаг б. Для каждого приращения А| вычисляем константу Еида

Р

7 = - -— »

_ 1 + в(Зы^,А6) - «

а затем поправку к Еектору Х(,Ц,,£) в Еиде ДХ(Лш^.Дё) =72:, где z - ранее вычисленный, Еектор.

Шаг 6 циклически повторяется для всех при этом требуется только вычислить константу 7 для нового А? и 5 элементов Еек-тора АХС.Ц^Д?) = 7 г, необходимых для вычисления всех еидое схемных функций, где Х(3шк,?0+А5) = Х^,^) - АХС^.А!).

Для ноеого параметра % процесс повторяется с 4-го шага. Рассмотрены также возможности проведения экспесс-анализа частотных характеристик с использованием.резольвент^ регулярно пучка. Эти методы распространены и на декомпозиционный подход.

III. ОСНОВНЫЕ ВЫВОДЫ ПО РАБОТЕ.

1.' Диссертационная работа посвящена актуальной проблеме минимизации вычислительных затрат и объема занимаемой под задачи оперативной памяти персональных ЭВМ для численно-аналитических методов моделирования радиоэлектронных схем аналоговой обработки сигналов.

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

2. В диссертации предложены две вычислительные схемы для эффективного вычисления алгебраической части решения линейных алгебра-дифференциальных систием. Первый алгоритм основан на предварительном накоплении скалярных произведений для спектральных компонент, в результате ке требуется хранения плотной матрицы для.выделения алгебраической части решения ЛАДСУ. Этот алгоритм может быть использован для алгебро-дифференциальных систем произвольного вида.

Второй алгоритм использует специфику строения матриц электронных схем, упрощены ранее известные преобразования. Предложен новый способ формирования уравнений для линейнозависимах индуктивных токов. Это позволяет минимизировать объем вычислений и получить блок А£0 без алгебраических операций, а также значительно упростить алгоритм решения ЛАДСУ для электронных схем.

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

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

Предлокен ноеый алгоритм определении кратности, основанный' на свойствах логарифма от детерминантной функции. Он позволяет устойчиво определять кратность корней е пределах б...10 и обеспечивает эффективное распознавание близких корней.

5. Исследованы и решены вопросы минимизации затрат оперативной памяти и объема -вычислений для многоЕариантных расчетов в частотной области. Предложена формула модификации матрицы, обратной к произвольной ^.-матрице, предстаЕИмой в виде суммы Х-матрицы единичного ранга с варьируемой скалярной функцией от параметра и X и регулярной ^.-матрицы, не зависящей от параметра. На основе этого соотношения и свойств элементарных матриц элементов, представимых в виде сумм скелетных произведений постоянных векторов фиксированной для элемента структуры, предлокен новый алгоритм быстрого построения семейств частотных характеристик в области вариаций параметров схемных элементов. Исследован также Еопрос о применении "сжатых декомпозиционных форм" к задачам многовариантного анализа.

6. На основе разработанных в'диссертации вычислительных схем были созданы программные модули для пакета схемотехнического проектирования "СПЕКТР", разрабатываемого в ФЙАП РАН в 1989-1992 г.г.; эти результаты частично использованы в НИИ радиоаппаратуры (г.Санкт-Пе-тербург), где аналогичный пакет разрабатывается для САПР арсенвд-галлиевых СВЧ-микросхем и модулей.

IV. ПУБЛИКАЦИИ ПО РАБОТЕ.

1. Голуб H.H., Михайлов В.В., У Суйцян. Декомпозиционный метод численно-аналитического решения алгебро-дифференциальных систем большого порядка и его применение в САПР ОИС СВЧ//Электродинамика.и техника СВЧ и КВЧ. - 1993.- Вып. 3.- С.18-29.

2. Михайлов В.В., Голуб H.H., У Суйцян. Декомпозщиснныэ метода численно-аналитического решения больших алгебро-дифферэтшальша систем //Проблемы автоматизированного моделирования в электронике: Тез. докл. науч.-техн. конф. - Киев: изд-е Общ-Еа "Знание" Украины, 1993. - С.17.

3. Михайлов В.Б., Сидоров К.В., У Суйцян. Реализация метода Ньютона-Канторовича для решения ' нелинейных алгебро-таМеретшалыш систем уравнений электронных схем //Проблемы автоматизированного модэлирсгания в электронике: Тез. докл. науч.-техн. конф. - Ккзг:

изд-е Общ-ва "Знание" Украины, 1993. - 0.18. 4'. Михайлов В.Б., У Суйцян. Спектральные задачи для регулярных разреженных пучков матриц в реализации численно-аналитических методов моделирования нелинейных схем //Проблемы йелинейной электротехники: Тез.докл. IV науч.-техн. конф. - Киев: изд-е ИПМЭ АН Украины, 1992. - 0. 89-90..

5. Оптимизация вычислений для численно-аналитических методов в пакетах схемотехнического проектирования /В.Б.Михайлов, Т.В.Мазюке-вич, И.Л.Михайлова, У Суйцян //Информатика. Сер. Автоматизация проектирования. - 1992,- Вып.4. - С.55-65.

6. У Суйцян, Голуб H.H., Мещанинов Е.Л. Повышение эффективности программного•обеспечения САПР РЭА в задачах многокритериальной оптимизации и многовариактного анализа //Информатика. Сер. Автоматизация проектирования. - 1993.- Вып.З.- С.34-44.

Личный вклад автора в результаты работы:

- предложено два способа минимизации объема вычислений и затрат памяти для численно-аналитического решения ЛАДСУ: для широкого круп приложений и с учетом структуры строения матриц схем (Еторой совместно с В.Б.Михайловым и Т.В.Мазюкевич);

- выполнено исследование интерполяционных методов; предложен комбинированный алгоритм, минимизирующий число итераций; предложен быстрый и надежный способ оценки кратности корней;

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

- предложен новая формула модификации резольвенты \-матрицы общегс вида, которую можно представить в виде суммы не .зависящей от параметра 5 регулярной ^.-матрица и зависящей от £ однорангчвой; совместно с Е.Л.Мещаниновым на ее основе разработан новый быстрый алгоритм построения семейств частотных характеристик для САПР РЭА;

- разработаны оценки эффективности вычислительных алгоритмов, реа-реализующее численно-аналитические методы решения ЛАДСУ;

- разработан ряд вычислительных программ на языке Си, включенных i состав прикладного пакета "СПЕКТР".

Подп. к П8Ч. 28.09.93. формат 60x8^/16. Офсетная печать. Печ. л. 1,0. Тираж 100 экз. Зак. № 204. Бесплатно. Отпечатано в МГП "Поляком" 197376, Санкт-Петербург, ул. Проф. Попова, 5