Высшая математика

Сложность булевых схем (Circuit Complexity): Архитектура вычислений

Когда мы оцениваем алгоритмы нотацией О-большое (O(N)), мы представляем Машину Тьюринга, которая последовательно выполняет код, считывая ленту туда и обратно. Но современные микропроцессоры работают иначе: это гигантские статичные графы из миллиардов транзисторов, по которым ток пробегает практически мгновенно. Для анализа аппаратной эффективности дискретная математика использует совершенно другую метрику — Сложность булевых схем.

Подробнее

Математическая логика и исчисление высказываний: строгий анализ

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

Подробнее

Теория множеств: Понятия, операции и диаграммы Эйлера-Венна

Теория множеств, созданная Георгом Кантором в конце XIX века, является языком и фундаментом всей современной математики. Множество — это одно из первоначальных, неопределяемых понятий математики. Интуитивно под множеством понимают совокупность, собрание, набор некоторых объектов, объединенных по какому-либо признаку. Объекты, составляющие множество, называются его элементами.

Подробнее

Булева алгебра и логические вентили: Фундамент вычислительной техники

Булева алгебра — раздел математической логики, в котором изучаются логические операции над высказываниями. Названа в честь английского математика Джорджа Буля. Особенность этой алгебры в том, что переменные могут принимать только два значения: "истина" (1) и "ложь" (0). Этот бинарный подход стал идеальной математической моделью для конструирования цифровых вычислительных машин и микропроцессоров.

Подробнее

Основы комбинаторики: Перестановки, размещения и сочетания

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

Подробнее

Введение в теорию графов: Основные понятия и применение

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

Подробнее

Эволюция численных методов: квантовые алгоритмы и алгоритм HHL для линейных систем

Квантовое превосходство в вычислительной линейной алгебре

Наш цикл из ста статей, посвященный классическим численным методам, логично завершить взглядом в будущее, где зарождается новая, революционная вычислительная парадигма — квантовые вычисления. Вся классическая математика, которую мы обсуждали (методы Гаусса, Крылова, многосеточные алгоритмы), опирается на архитектуру процессоров фон Неймана и детерминированные биты, принимающие значения 0 или 1. Как бы мы ни оптимизировали эти алгоритмы, решение системы из N линейных алгебраических уравнений (СЛАУ) всегда будет требовать времени, по меньшей мере пропорционального количеству неизвестных O(N). Компьютеру банально нужно время, чтобы просто прочитать все числа из памяти.

В 2009 году физики Арам Харроу, Авинатан Хасидим и Сет Ллойд опубликовали алгоритм HHL (Harrow-Hassidim-Lloyd algorithm), который вызвал настоящий шок в академическом мире. Этот квантовый алгоритм предназначен для решения систем линейных уравнений Ax = b. Его теоретическая вычислительная сложность составляет феноменальные O(log N)! Экспоненциальное ускорение означает, что система из триллиона уравнений, на которую лучшему классическому суперкомпьютеру потребовались бы годы работы, квантовый компьютер сможет решить за доли секунды. Как возможна такая математическая магия?

Суперпозиция, фазовая оценка и квантовое состояние

Квантовый компьютер работает не с обычными регистрами, а с кубитами, которые находятся в суперпозиции (одновременно во всех возможных состояниях от 0 до 1). Алгоритм HHL не вычисляет вектор решения x в виде обычного массива чисел. Он кодирует правую часть уравнения b в квантовое состояние регистра (амплитуды вероятностей), а затем с помощью квантовых вентилей трансформирует это состояние так, чтобы оно пропорционально отражало вектор решения x.

Главный математический механизм HHL основан на Квантовой оценке фазы (Quantum Phase Estimation, QPE). Алгоритм симулирует квантовую гамильтонову эволюцию матрицы A во времени (оператор exp(iAt)). Применяя квантовое преобразование Фурье (QFT), алгоритм «извлекает» собственные значения матрицы A в специальный вспомогательный регистр кубитов. Затем применяется контролируемый поворот кубита, который физически делит амплитуды на эти собственные значения (эквивалент инвертирования матрицы A^-1). Наконец, обратная фазовая оценка возвращает систему из спектрального пространства, выдавая готовое квантовое состояние |x> = A^-1 |b>.

Проблема извлечения данных и перспективы

Квантовое ускорение HHL содержит серьезные практические оговорки (caveats). Вы не можете просто «распечатать» полученный миллиономерный вектор решения на экран. Квантовая механика позволяет вам только произвести измерение состояния, что разрушит суперпозицию и выдаст лишь одно случайное число. Алгоритм HHL полезен не тогда, когда вам нужны все значения x, а тогда, когда вам нужно найти глобальное свойство решения (например, скалярное произведение x*M*x или среднюю кинетическую энергию системы).

Кроме того, матрица A должна быть разреженной (sparse) и хорошо обусловленной, а данные правой части b должны загружаться в компьютер с помощью сверхбыстрой квантовой памяти (QRAM), которая пока не существует на аппаратном уровне. Несмотря на эти технические преграды, алгоритм HHL заложил фундамент для Квантового Машинного Обучения (QML). Решение гигантских СЛАУ лежит в основе методов наименьших квадратов, обучения нейросетей и дифференциальных уравнений Навье-Стокса. Как только квантовые процессоры преодолеют барьер ошибок (Quantum Error Correction), алгоритмы типа HHL полностью перепишут правила игры в вычислительной физике, экономике и криптографии.

Подробнее

Метод моментов в электродинамике (MoM): численное решение интегральных уравнений

Как рассчитать антенну мобильного телефона?

В мире вычислительной электродинамики, помимо дифференциальных сеточных методов вроде FDTD (Метод конечных разностей во временной области), существует мощнейший альтернативный класс численных алгоритмов. Когда инженерам необходимо спроектировать сложную проволочную антенну (как на Wi-Fi роутере), рассчитать эффективную площадь рассеяния (ЭПР) истребителя-невидимки или спроектировать микрополосковую плату смартфона, классические 3D-сетки FDTD оказываются крайне неудобными. Моделирование тонких проводов толщиной в доли миллиметра в свободном безграничном пространстве требует слишком мелкой объемной сетки и абсурдного расхода памяти.

В этих случаях индустрия обращается к интегральной формулировке уравнений Максвелла. Физическая суть этой формулировки заключается в законе Био-Савара-Лапласа и потенциалах: электрические токи, текущие по металлическим поверхностям антенны, излучают электромагнитное поле. Интегральное уравнение (например, EFIE — уравнение электрического поля) связывает неизвестное распределение токов на поверхности металла с заданным падающим возбуждающим полем (например, от кабеля питания). Для численного решения этого интегрального уравнения в 1968 году Роджер Харрингтон формализовал универсальный алгоритм, названный Методом моментов (Method of Moments, MoM).

От физического интеграла к матрице сопротивлений

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

Затем интегральное уравнение умножается на весовые (тестовые) функции и интегрируется по всей поверхности детали. В результате этой математической операции бесконечномерное интегральное уравнение превращается в плотную систему линейных алгебраических уравнений (СЛАУ): [Z] * [I] = [V]. В этой формуле вектор [I] — это неизвестные токи, вектор [V] — напряжения (возбуждение), а гигантская матрица [Z] имеет глубочайший физический смысл. Она называется обобщенной матрицей взаимных импедансов (сопротивлений). Каждый элемент этой матрицы описывает электромагнитное влияние (излучение) одной базисной функции тока на другую через открытое пространство.

Сингулярности функции Грина и открытое пространство

Вычисление элементов матрицы импедансов [Z] является самой сложной и ресурсоемкой частью Метода моментов. Внутри интегралов содержится функция Грина свободного пространства (ядро интегрального оператора), которая имеет вид exp(-ikr)/r. Эта функция обратно пропорциональна расстоянию (r) между током источника и точкой наблюдения. Если мы вычисляем самовоздействие элемента (то есть расстояние r стремится к нулю), функция уходит в бесконечность!

Попытка вычислить такой сингулярный интеграл обычным методом Гаусса даст математический мусор. Инженерам приходится использовать специальные аналитические методы выделения особенности для точного вычисления диагональных элементов матрицы. Огромным, неоспоримым преимуществом MoM является то, что этот алгоритм автоматически и идеально строго учитывает условие излучения Зоммерфельда на бесконечности. Волна беспрепятственно улетает в космос, и алгоритму не нужны никакие искусственные поглощающие слои (PML) на границах расчетной области. Сегодня алгоритм MoM (часто ускоренный Быстрым мультипольным методом FMM для борьбы с плотной матрицей) лежит в основе ведущих радиотехнических САПР, таких как Altair FEKO и CST Microwave Studio.

Подробнее

Интерполяция Эрмита: учет значений функции и ее производных в геометрии

Недостатки классической интерполяции Лагранжа

Как мы уже изучали в разделе об аппроксимации функций, классический интерполяционный многочлен Лагранжа строится так, чтобы его график строго проходил через заданный набор дискретных точек (узлов). Однако в инженерном проектировании, компьютерной графике (CAD) и вычислительной гидродинамике простого прохождения кривой через точки часто бывает недостаточно. Представьте, что вы проектируете профиль автомобильной дороги или траекторию движения резца станка с ЧПУ. Если вы используете полином Лагранжа, кривая пройдет через все контрольные точки, но в самих этих точках ее наклон (первая производная) или кривизна (вторая производная) могут изменяться непредсказуемым и диким образом, порождая рывки и изломы скорости.

Инженеру необходимо жестко контролировать не только то, ГДЕ должна оказаться кривая в данный момент времени, но и КУДА она должна быть направлена (какова ее скорость и ускорение). Эту фундаментальную задачу решает метод интерполяции Шарля Эрмита. Алгоритм Эрмита обобщает интерполяцию Лагранжа на случай, когда в узлах сетки известны (и должны строго соблюдаться) не только значения самой функции, но и значения ее производных до заданного порядка.

Разделенные разности с кратными узлами

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

Когда алгоритм пытается вычислить разделенную разность первого порядка (скорость изменения функции) между двумя одинаковыми продублированными узлами, в знаменателе дроби возникает ноль: (x_i - x_i). Но мы знаем из математического анализа, что предел отношения приращения функции к приращению аргумента — это и есть производная! Поэтому алгоритм просто заменяет эту неопределенность 0/0 на заданное нам известное значение производной в этой точке. Аналогично, если задана вторая производная (ускорение), узел дублируется трижды. В результате мы получаем единый полином высокой степени, который идеально ложится на все точки и векторы касательных.

Кубические сплайны Эрмита и сплайны Акимы

Глобальный многочлен Эрмита высокой степени (как и многочлен Лагранжа) страдает от феномена Рунге — катастрофических осцилляций на краях отрезка. Поэтому в индустрии повсеместно применяются кусочно-полиномиальные кривые — кубические сплайны Эрмита.

На каждом интервале между двумя точками строится отдельный полином 3-й степени, который жестко фиксируется 4 условиями: двумя значениями функции по краям и двумя значениями производных по краям. В отличие от обычного кубического сплайна, где производные вычисляются алгоритмом глобально (через решение СЛАУ для обеспечения гладкости второй производной во всех точках), в сплайнах Эрмита производные задаются локально и вручную инженером (или локальными эвристиками). Одной из самых знаменитых реализаций является Сплайн Акимы (Hiroshi Akima, 1970). Алгоритм Акимы вычисляет производные в узлах локально, опираясь на геометрию нескольких соседних точек. В результате сплайн Акимы практически не подвержен паразитным выбросам (overshoots) и изломам в местах резкого изменения данных, являясь золотым стандартом для интерполяции физических табличных данных (например, термодинамических свойств газов) без искусственных осцилляций.

Подробнее

Вычислительная алгебраическая геометрия: базисы Грёбнера и полиномиальные системы

Когда метод Ньютона бессилен

Решение систем нелинейных уравнений — одна из сложнейших задач численного анализа. Если система состоит из многочленов (полиномиальная система), она возникает в криптографии, робототехнике (обратная кинематика манипуляторов), компьютерном зрении и молекулярной химии. Обычно для таких систем применяют многомерный метод Ньютона-Канторовича. Но метод Ньютона — локальный. Он найдет лишь один корень вблизи начальной точки. Что если инженеру нужно найти строго все корни системы (или доказать, что их вообще не существует)? Что если корней бесконечно много и они образуют кривые поверхности (алгебраические многообразия)? Здесь численные приближения пасуют, и в дело вступает вычислительная коммутативная алгебра.

Революционным прорывом в этой области стало создание в 1965 году Бруно Бухбергером (в его докторской диссертации под руководством Вольфганга Грёбнера) алгоритма построения базисов Грёбнера. Этот алгоритм стал для нелинейных полиномиальных систем тем же, чем является алгоритм Гаусса для линейных систем уравнений. Он позволяет строго алгоритмически, за конечное число шагов, преобразовать любую сложную систему полиномов в эквивалентную ей систему, но имеющую особую, «удобную» треугольную форму.

Алгоритм Бухбергера: нелинейный аналог исключения Гаусса

Основная идея Бухбергера опирается на понятие идеала в кольце многочленов (множества всех полиномов, которые обращаются в ноль там же, где и исходные уравнения). Любая система задает свой базис этого идеала. Базис Грёбнера — это такой «идеальный» базис, в котором старшие члены полиномов обладают специальным свойством делимости.

Алгоритм Бухбергера берет пары исходных полиномов и вычисляет их S-полиномы (специальные комбинации, в которых искусственно уничтожаются старшие степени, подобно обнулению коэффициентов в методе Гаусса). Затем эти S-полиномы делятся на исходный базис с остатком. Если остаток не равен нулю, он добавляется в систему как новое уравнение (не меняющее корней!). Этот процесс генерации новых полиномов продолжается до тех пор, пока все возможные остатки не станут нулями. Теорема Гильберта о базисе гарантирует, что этот процесс обязательно остановится.

Триумф лексикографического порядка

Самая мощная магия базисов Грёбнера раскрывается при использовании лексикографического порядка сортировки одночленов (как слова в словаре). Если мы вычислим базис Грёбнера с таким порядком, то в полученной эквивалентной системе уравнений последний полином будет содержать только одну неизвестную переменную (например, только z)! Предпоследний полином будет содержать z и y, и так далее. Мы получаем строго треугольную систему.

Теперь решение нелинейной многомерной системы сводится к банальному вычислению корней одного полинома от одной переменной (что можно сделать численно с огромной точностью), а затем обратной подстановкой найденных значений в верхние уравнения системы. Алгоритм Бухбергера, интегрированный в системы компьютерной алгебры (Maple, Mathematica), требует гигантских объемов памяти (сложность алгоритма часто дважды экспоненциальная EXPSPACE), но его способность находить абсолютно все скрытые корни сделала его незаменимым аналитическим инструментом современной прикладной геометрии.

Подробнее