Целочисленные точки в выпуклых многогранниках

Исследование целых точек в выпуклых многогранниках ^[1] мотивируется такими вопросами, как «сколько неотрицательных целочисленных решений имеет система линейных уравнений с неотрицательными коэффициентами» или «сколько решений имеет целочисленная линейная программа ». Подсчет целых точек в многогранниках или другие вопросы, связанные с ними, возникают в теории представлений , коммутативной алгебре , алгебраической геометрии , статистике и информатике . ^[2]

Множество целочисленных точек или, в более общем смысле, множество точек аффинной решетки в многограннике называется Z-многогранником . ^[3] из математической записи $\mathbb {Z}$ или Z для набора целых чисел. ^[4]

Характеристики

Для решетки Λ теорема Минковского связывает число d(Λ) (объем фундаментального параллелепипеда решетки) и объем данного симметричного выпуклого множества S с количеством точек решетки, содержащихся в S .

Количество точек решетки, содержащихся в многограннике, все вершины которого являются элементами решетки, описывается многочленом Эрхарта многогранника . Формулы для некоторых коэффициентов этого многочлена также включают d(Λ).

Приложения

Оптимизация цикла

В некоторых подходах к оптимизации цикла набор выполнений тела цикла рассматривается как набор целочисленных точек в многограннике, определенном ограничениями цикла.

См. также

Ссылки и примечания

^ В некоторых контекстах выпуклые многогранники называют просто «многогранниками».
^ Целые точки в многогранниках. Геометрия, теория чисел, теория представлений, алгебра, оптимизация, статистика , совместная летняя исследовательская конференция ACM-SIAM, 2006 г.
^ Термин «Z-многогранник» также используется как синоним выпуклого решетчатого многогранника , выпуклой оболочки конечного числа точек в аффинной решетке.
^ «Вычисления в итерированных пространствах» в: Справочник по проектированию компиляторов: оптимизации и генерация машинного кода, CRC Press 2007, 2-е издание, ISBN 1-4200-4382-X , стр. 15-7.

Дальнейшее чтение

Барвинок, Александр ; Бек, Матиас; Хаазе, Кристиан; Резник, Брюс ; Велкер, Фолькмар (2005), Целые точки в многогранниках: материалы совместной летней исследовательской конференции AMS-IMS-SIAM, состоявшейся в Сноуберде, Юта, 13–17 июля 2003 г. , Contemporary Mathematics, vol. 374, Провиденс, Род-Айленд: Американское математическое общество, номер документа : 10.1090/conm/374 , ISBN. 0-8218-3459-2 , МР 2134757
Барвинок, Александр (2008), Целые точки в многогранниках , Цюрихские лекции по высшей математике , Цюрих: Европейское математическое общество, номер документа : 10.4171/052 , ISBN 978-3-03719-052-4 , МР 2455889
Бек, Матиас; Хаазе, Кристиан; Резник, Брюс ; Вернь, Мишель ; Велкер, Фолькмар; Ёсида, Рюрико (2008), Целые точки в многогранниках: геометрия, теория чисел, теория представлений, алгебра, оптимизация, статистика (PDF) , Современная математика, том. 452, Провиденс, Род-Айленд: Американское математическое общество, номер документа : 10.1090/conm/452 , ISBN. 978-0-8218-4173-0 , МР 2416261

[1] В некоторых контекстах выпуклые многогранники называют просто «многогранниками».

[2] Целые точки в многогранниках. Геометрия, теория чисел, теория представлений, алгебра, оптимизация, статистика , совместная летняя исследовательская конференция ACM-SIAM, 2006 г.

[3] Термин «Z-многогранник» также используется как синоним выпуклого решетчатого многогранника , выпуклой оболочки конечного числа точек в аффинной решетке.

[4] «Вычисления в итерированных пространствах» в: Справочник по проектированию компиляторов: оптимизации и генерация машинного кода, CRC Press 2007, 2-е издание, ISBN 1-4200-4382-X , стр. 15-7.

[1]

[2]

[3]

[4]