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

Одним из вариантов применения остовных деревьев с низким растяжением служит решение систем линейных уравнений с симметричными матрицами с диагональным преобладанием. Боман и Хендриксон [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> и до O(n(log nloglog n)2 log(l/e)) в случае, если системы планарны. Используя недавно разработанную редукцию Бомана, Хендриксона и Вавасиса [ ], можно получить алгоритм решения систем линейных уравнений, возникающих при применении метода конечных элементов для решения двумерных эллиптических уравнений в частных производных, с временем исполнения O(n(logn loglog n)2log(l/e)).