Max Home IndustryРешение общего линейного уравнения является более чем квадратичным по размеру матрицы, но если оно имеет конкретную форму, теперь вы можете выполнить эту работу почти за линейное время. Этот прорыв не только быстрее, он проще и имеет множество применений.
Задача симметричного диагонального доминанта (SDD) состоит в том, чтобы найти x в Ax = b с таким A, чтобы его диагональные элементы были больше, чем сумма значений всех недиагональных элементов в матрице. То есть SDD-матрица симметрична и имеет большие диагональные элементы по сравнению с остальными.
Проблемы с матрицей SDD возникают естественным образом во многих ситуациях — в электрических сетях, моделях конечных элементов, компьютерном зрении и многом другом. Несколько более специализированная форма матрицы SDD — это лапласиан графа. Это связано с изучением графов, и это разница между матрицей степеней D и матрицей смежности A:
L = D-A
Матрица степеней — это просто количество ребер, инцидентных каждой вершине dii, то есть диагональная матрица. Матрица смежности имеет силу связи между вершиной i и вершиной j как ее элементы с диагональю, установленной на ноль.
Интерпретация того, что означает сила связи, варьируется в зависимости от субъекта. Например, для электрической сети сила связи — это проводимость. Решение лапласианской проблемы связано с потоком в сети, представленной графом.
Когда вы впервые встречаетесь с ним, трудно понять, какое отношение имеет лапласиан к чему-либо, но его можно рассматривать как дискретный аналог обычного оператора Лапласа. Рассмотрим на мгновение график в виде прямоугольной сетки с силой соединения, равной единице. Каждая вершина имеет четыре входных ребра, поэтому D представляет собой диагональную матрицу из четверок, и в каждой строке A есть четыре единицы, указывающие на связи с четырьмя соседями. Если вы примените L, то есть D-A, к вектору единиц, каждый элемент вектора сопоставлен с:
4aij- ai-1j- ai + 1j- aij-1- aij + 2
Это обычное дискретное приближение к двумерному оператору Лапласа. Матрица Лапласа является обобщением оператора Лапласа на более общие графы.
Это отождествление матрицы Лапласа, оператора Лапласа и графика — удивительный и глубокий математический элемент. Однако для этого метода решения важна связь между матрицей Лапласа и структурой графа. Это то, что используется для решения Lx = b за почти линейное время.
Стоит отметить, что не все матрицы SDD являются лапласианами некоторого графа, но они могут быть преобразованы в связанный лапласиан, который затем дает решение исходной проблемы SDD.
Группа исследователей Массачусетского технологического института в статье, которая будет представлена на симпозиуме ACM по теории вычислений в этом году, представляет гораздо более простой и быстрый алгоритм, чем его предшественники. Более раннее почти линейное решение требовало 130 страниц и достижений в теории спектральных графов. По словам изобретателей, нынешний метод можно уместить на доске. Есть надежда, что, поскольку метод намного проще, практикам будет легче адаптировать его к своим потребностям.
Пример остовного дерева с низкой степенью растяжения (зеленый) v Остовное дерево с невысокой степенью растяжения (красный)
Метод работает, находя остовное дерево с малым растяжением, то есть такое, которое имеет короткие пути между вершинами, а затем использует его для создания более разреженного графа. На каждом этапе решается граф, чтобы дать поток в сокращенной сети. Последовательность таких графиков приводит к решению с произвольной точностью. Стоит отметить, что решение не является точным, но приближение может быть выполнено с любой точностью, а алгоритм масштабируется практически в линейное время с размером матрицы m, n:
O (m log2n log log n log (ε-1))
Вы можете прочитать подробности в статье, но важным моментом, который она демонстрирует, является замечательная связь между теорией графов и линейной алгеброй. Это также должно сделать более практичным решение больших линейных задач SDD без необходимости использования суперкомпьютера.