Остовные деревья с низким растяжением: различия между версиями

Одним из вариантов применения остовных деревьев с низким растяжением служит решение систем линейных уравнений с симметричными матрицами с диагональным преобладанием. Боман и Хендриксон [5] первыми открыли удивительную связь между этими, на первый взгляд, совершенно разными задачами. Они применили остовные деревья из работы [2] для разработки алгоритмов решения задач с временем исполнения <math>m^{3/2} 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) </math>. Шпильман и Тенг [14] улучшили их результат, продемонстрировав использование остовных деревьев [2] для решения систем линейных уравнений с диагональным преобладанием за время <math>m 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) </math>.

Применяя остовные деревья с низким растяжением, предложенные в [9], можно уменьшить время решения таких систем линейных уравнений до <math>m log^{O(1)} n log(1 / \epsilon) \;</math>, а в случае, если системы планарны – до <math>O( n(log \; n \; log \; log \; n ) log (1 / \epsilon)) </math>. Используя недавно разработанную редукцию Бомана, Хендриксона и Вавасиса [6], можно получить алгоритм решения систем линейных уравнений, возникающих при применении метода конечных элементов для решения двумерных эллиптических уравнений в частных производных, с временем исполнения <math>O(n(log \; n \; log \; log \; n)^2 log(l / \epsilon))</math>.