Вложенное рассечение на регулярной сетке

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

Редактировать Я только что обнаружил, что есть код, который делает это: http://www.cise.ufl.edu/research/sparse/meshnd/

Да. Я недавно написал код, чтобы сделать именно это.

Предположим, у вас есть $n_x \times n_y$сетка, и что допустимо иметь листовые узлы с 100 вершинами. Затем можно определить рекурсивную функцию, аргументами которой являются:

• размеры и смещения прямоугольного субдомена
• указатель на массив, который будет хранить переупорядочение

Затем подпрограмма просто должна вычислить произведение локальных измерений, чтобы решить, является ли домен приемлемо малым, чтобы быть листом, и затем, если это так, записать натуральные индексы узла листа (скажем, $\mathrm{natural}(x,y)=x+y n_x$ для $n_x \times n_y$ сетка), в противном случае вырежьте наибольшее измерение поддоменов, рекурсируйте на левой и правой частях, а затем запишите натуральные индексы разделителя.