Компоновка схемы: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 65: Строка 65:




Глобальный минимум <math>\Phi (x) \;</math> можно найти, решив разреженную систему линейных уравнений с симметричной положительно определенной матрицей <math>\mathbf{Q} \mathbf{x} + \mathbf{c} = 0 \;</math> (предполагая, что имеется более одной фиксированной вершины), которая поддается эффективному решению с достаточной точностью при помощи любого числа итеративных алгоритмов решения. Квадратичная компоновка может иметь различные оптимумы в зависимости от модели (клика либо звезда), используемой для представления гиперребер. Однако для k-точечного гиперребра имеет место следующий факт: если вес 2-точечных ребер задается равным <math>W_c \;</math> в модели с кликой и <math>kW_c \;</math> в модели со звездой, то для случая квадратичной компоновки эти модели эквивалентны [7].
Глобальный минимум <math>\Phi (x) \;</math> можно найти, решив разреженную систему линейных уравнений с симметричной положительно определенной матрицей <math>\mathbf{Q} \mathbf{x} + \mathbf{c} = \mathbf{0} \;</math> (предполагая, что имеется более одной фиксированной вершины), которая поддается эффективному решению с достаточной точностью при помощи любого числа итеративных алгоритмов решения. Квадратичная компоновка может иметь различные оптимумы в зависимости от модели (клика либо звезда), используемой для представления гиперребер. Однако для k-точечного гиперребра имеет место следующий факт: если вес 2-точечных ребер задается равным <math>W_c \;</math> в модели с кликой и <math>kW_c \;</math> в модели со звездой, то для случая квадратичной компоновки эти модели эквивалентны [7].




'''Линеаризованная квадратичная компоновка'''
'''Линеаризованная квадратичная компоновка'''


Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя wij = 1/jxi — xjj на каждой итерации. Другим вариантом может быть решение единичной /S-регуляризованной задачи оптимизации, заданной формулой Ф^(х) = minx Pi;j wij(xi - xj)2 + fi, /3 > 0 – например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1].
Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя <math>w_{ij} = \frac{1}{|x_i - x_j|} \;</math> на каждой итерации. Другим вариантом может быть решение единичной <math>\beta \;</math>-регуляризованной задачи оптимизации, заданной формулой <math>\Phi(\mathbf{x}) = min_x \sum_{i,j} w_{ij} \sqrt{(x_i - x_j)^2 + \beta} , \beta > 0 \;</math> – например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1].




Компоновка с учетом полной длины проводов полупериметра (HPWL)
'''Компоновка с учетом полной длины проводов полупериметра (HPWL)'''


Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять /S-регуляризацию [1]. Для m-точечного гиперребра (при m > 3) можно переформулировать HPWL в виде максимума (по норме L1) среди всех m(m — 1)/2 попарных расстояний jxi — xjj и аппроксимировать L1-норму Lp-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме 0, что впоследствии убирается при помощи /S-регуляризации. Полученная аппроксимация HPWL задается формулой Pfwf;H(f)(xH(f) — xf)2. Каждая неподвижная точка f вводит квадратичный член WF;H(F) (xH(f) —xf)2-. Манипулируя положениями неподвижных точек, можно добиться того, что компоновка будет удовлетворять целевым ограничениям плотности. По сравнению с постоянно действующими силами неподвижные точки повышают контролируемость и стабильность итераций алгоритма компоновки [ ].
Функция HPWL может быть доказуемо аппроксимирована строго выпуклыми и дифференцируемыми функциями. Для 2-точечных гиперребер можно применять /S-регуляризацию [1]. Для m-точечного гиперребра (при m > 3) можно переформулировать HPWL в виде максимума (по норме L1) среди всех m(m — 1)/2 попарных расстояний jxi — xjj и аппроксимировать L1-норму Lp-нормой (p-м корнем из суммы p-х степеней). Это позволяет устранить недифференцируемость при всех значениях, кроме 0, что впоследствии убирается при помощи /S-регуляризации. Полученная аппроксимация HPWL задается формулой Pfwf;H(f)(xH(f) — xf)2. Каждая неподвижная точка f вводит квадратичный член WF;H(F) (xH(f) —xf)2-. Манипулируя положениями неподвижных точек, можно добиться того, что компоновка будет удовлетворять целевым ограничениям плотности. По сравнению с постоянно действующими силами неподвижные точки повышают контролируемость и стабильность итераций алгоритма компоновки [ ].
4551

правка

Навигация