Во время работы над программами LazPhCoord и LazDiscret2 я столкнулся с необходимостью формирования и решения уравнений с разреженными матрицами коэффициентов, которые получаются при использовании модифицированного метода узловых потенциалов. Как отмечается в [1] квадратная матрица называется разреженной, если лишь небольшая часть (например 20-30%) ее элементов отлична от нуля.

Применение ММУП значительно увеличивает разреженность матрицы, даже для простейших схем с числом узлов до 10 заполненность основной матрицы составляет не более 25%. С увеличением числа узлов заполненность основной матрицы коэффициентов становится еще меньше — 5% и менее при числе узлов 100 и более

Изучение вопроса возможности решения квадратно-матричных уравнений неизбежно приводит к пакету Sparse, который широко используется в симуляторах цепей и особенно подходит для обработки матриц проводимостей, получаемых  при использовании метода узловых потенциалов (МУП) и модифицированного МУП. Написанный на С пакет Sparse версии 1.3 применяется в течение многих лет, особенно в сообществе EDA (средства разработки электроники). За это время он работал хорошо с очень небольшим количеством проблем.

Изменения, внесенные в следующую версию Sparse1.4 (Copyright © 2003, Kenneth S. Kundert), в основном преследовали цель привести исходный код пакета в соответствие современным стандартам языков С и С++. Кроме того Sparse1.4 формально стал проектом с открытым исходным кодом, который можно найти на sourcforge.net (http://sparse.sourceforge.net).

Так как все мои разработки были выполнены на FreePascal, то я решил адаптировать — фактически перевести — исходный код пакета Sparse1.4 на этот язык. В результате был разработан модуль fpcSparse1_4.pas, который предлагается в прилагаемом файле.

Содержание прилагаемого архива

Введение Sparse1.4 User's Guide  (перевод Заволока О., 2018)

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

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

Sparse был изначально написан для использования в симуляторах цепей и особенно подходит для обработки матриц проводимостей, получаемых  при применении метода узловых потенциалов (МУП) и модифицированного МУП. Линейные системы, генерируемые в симуляторе цепей, основаны на решении больших систем нелинейных уравнений с использованием метода Ньютона и интегрировании больших жестких систем обыкновенных дифференциальных уравнений. Поскольку используются итерационные подходы, Sparse оптимизирован для повторного решения матриц с одинаковой структурой. Тем не менее, Sparse также подходит для других целей.

Особенности Sparse1.4

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

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

[ Скачать с сервера (10.12 Mb) ]

1. Чуа Л.О., Лин Пен-Мин. Машинный анализ электронных схем: Алгоритмы и вычислительные методы. - М.: Энергия, 1980