Область применения
Основная область применения «Алгоритмической математики»: численное моделирование систем с распределенными параметрами, которые описываются уравнениями в частных производных. Такая система может включать в себя также и сосредоточенные объекты, описываемые обыкновенными дифференциальными либо алгебраическими уравнениями.
Объект с распределенными параметрами имеет бесконечное число степеней свободы. Его имитация в виде компьютерной дискретной модели для достижения необходимой точности требует рассмотрения большого числа дискретных элементов (точек или конечных элементов), характеризующих распределенный объект. Соответственно уравнения в частных производных заменяются большими системами алгебраических уравнений, описывающих дискретную модель.
В первую очередь нас интересуют наиболее практически важные задачи оптимизации больших систем, а также обратные задачи. Речь идёт о минимаксных задачах большой мерности с ограничениями, относящихся к нелинейному и целочисленному программированию.
Наш подход к решению проблем моделирования больших систем является антагонистическим по отношению к распространенной традиции, сложившейся за последние десятилетия развития вычислительной техники. Как известно, эта традиция состоит в попытке компенсировать недостаточное качество реализации алгоритмов и методов, за счёт необоснованно высокой утилизации ресурсов аппаратных средств, или простыми словами «патронов не жалеть».
Появившийся в нашей группе термин «сквозная оптимизация» означает экстремальную оптимизацию производительности на различных логических уровнях при выполнении математических расчётов: от высокоуровневого базового алгоритма и до нижнего уровня выполняемого машинного кода. Такую оптимизацию применительно к задачам математического программирования можно разделить на три уровня:
На «верхнем» уровне: применение новых теоретических методов, обеспечивающих кардинальное снижение вычислительной сложности решаемой задачи.
На «среднем» уровне: применение новых методов эффективного распараллеливания алгоритмов, которые ранее не поддавались распараллеливанию.
На «нижнем» уровне: применение собственных низкоуровневых библиотек, оптимизирующих массовые операции, нативные для уровней 1 и 2. Оптимизация осуществляется за счёт: векторизации вычислений, оптимизации потоков данных для кэш-памяти и оперативной памяти, максимального параллелизма операций, выполняемых каждым ядром.
Методы «Алгоритмической математики» разработаны на стыке когнитивных информационных технологий и Диакоптики Габриеля Крона. Метод декомпозиции с приёмом «пересечения слоя» был модернизирован с целью учёта трансформирующихся топологических структур, а также повышения быстродействия.
В части когнитивных информационных технологий рассматриваются не новомодные направления типа когнитивных интерфейсов мозг-машина, когнитивных ассистентов или виртуальной реальности.
Напротив, в «Алгоритмической математике» когнитивные технологии применяются для формализации знаний в области точных наук и инженерных приложений, а также для возможности формализованного оперирования этими знаниями программной системой. Это позволяет программно автоматически осуществлять анализ (многоуровневую рекурсивную декомпозицию на подсхемы) «большой системы» и синтезировать оптимальный алгоритм моделирования с целью минимизации его вычислительной сложности.
Разработанные методы оптимизации алгоритма под конкретный «сложный объект» обеспечивают радикальное снижение объема вычислений.
Практический пример «большой системы».
На стартовой странице нашего сайта в качестве примера «большой системы» выбраны газотранспортные системы (ГТС). На этом примере охарактеризуем вычислительную сложность возникающих задач.
ГТС содержит различные элементы, из них основные: газоперекачивающие агрегаты (ГПА) и линейные участки (трубы).
При составлении численной модели основной объем уравнений обеспечивают линейные участки. Это элемент с распределенными параметрами, описывается нелинейными уравнениями движения газа с частными производными. ГПА – это объект с сосредоточенными параметрами, который характеризуется большим количеством технологических ограничений.
Рассмотрим задачу оптимизации режимов работы ГТС, представленную в разделе «КОРТ–ДУ» нашего сайта. Она получила собственное название «Оптимизация ГТС». Речь идёт о расчёте плана оптимального управления ГТС, например, на сутки вперед. Оптимизация может быть параметрическая и/или структурная. В первом случае требуется подобрать управляющие воздействия (т.н. «уставки») для всех ГПА, и графики изменения уставок во времени, с целью экономии энергоресурсов в целом по ГТС. Или с целью достижения иного критерия оптимизации. При структурной оптимизации требуется определить коммутации оборудования, оптимизирующие топологию рабочей схемы ГТС.
На практике требуется решать задачи и параметрической, и структурной оптимизации ГТС совместно.
Пусть ГТС содержит 500 ГПА, и 10 тыс. км труб большого диаметра.
Задачи этого класса не могут рассчитываться последовательно во времени и «пошагово». Весь режим работы ГТС подлежит оптимизации единовременно в общем консолидированном расчёте. В результате численная модель будет иметь порядка 2-х миллионов узловых точек и порядка четверти миллиона неравенств, задающих технологические ограничения. Матмодель существенно нелинейная, функция цели также. Положение дополнительно осложняется требованиями структурной оптимизации.
Если абстрагироваться от требований по структурной оптимизации топологии схемы ГТС, то построение плана оптимального управления ГТС прежними методами можно осуществить однотипными итерациями, на каждой из которых потребуется выполнять операции:
Линеаризация и дискретизация матмодели ГТС, формирование цифровой модели ГТС.
Ввод дополнительных ограничений, удерживающих линейную модель в рамках её адекватности.
Выполнение матричных операций над матрицами, содержащими миллионы уравнений.
Решение задачи линейного программирования с учетом сотен тысяч неравенств. Потребуются сотни тысяч внутренних итераций симплекс-метода.
Количество таких итераций верхнего уровня оценить практически невозможно. В силу нелинейности задачи невозможно вообще гарантировать сходимость этого процесса.
Методы ускорения вычислений, полученные в «Алгоритмической математике», позволяют рассчитать задачу «Оптимизация ГТС» для приведенного примера ГТС на сервере производительностью 1 терафлопс за несколько минут. При этом обеспечивается линейный рост вычислительной сложности по мере увеличения ГТС, и кубический – при увеличении временн`ого интервала оптимизации.
Расчёт задачи «Оптимизация ГТС» обеспечивается впервые.
В разделе «КОРТ–АСУ ТП» описывается задача «Идентификация ГТС». Это обратная задача, которая обеспечивает полноту и достоверность информации о режимах работы ГТС и параметрах её элементов. По своей вычислительной сложности она сопоставима с задачей «Оптимизация ГТС».
Расчёт задачи «Идентификация ГТС» также обеспечивается впервые.
Аппарат «Алгоритмической математики» может применяться в различных прикладных областях. Например, при проектировании новой сложной техники. Для оптимизации её технических характеристик и сокращения времени разработки.