Изучение целочисленных точек в выпуклых многогранниках [1] мотивируется такими вопросами, как «сколько неотрицательных целочисленных решений имеет система линейных уравнений с неотрицательными коэффициентами» или «сколько решений имеет целочисленная линейная программа ». Подсчет целых точек в многогранниках или другие вопросы о них возникают в теории представлений , коммутативной алгебре , алгебраической геометрии , статистике и информатике . [2]
Множество целых точек, или, в более общем случае , множество точек на аффинной решетке , в многогранника называется Z-многогранника , [3] из математических обозначенийили Z для набора целых чисел. [4]
Характеристики
Для решетки Л, теорема Минковского связывает число й (Л) и объем симметричного выпуклого множества 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, 374 , Providence, RI: American Mathematical Society, DOI : 10,1090 / conm / 374 , ISBN 0-8218-3459-2, Руководство по ремонту 2134757
- Барвинок, Александр (2008), Целочисленные точки в многогранниках , Цюрихские лекции по высшей математике, Цюрих: Европейское математическое общество, DOI : 10.4171 / 052 , ISBN 978-3-03719-052-4, MR 2455889
- Бек, Матиас; Хаасе, Кристиан; Резник, Брюс ; Вернь, Мишель ; Велкер, Фолькмар; Йошида, Рюрико (2008), Целочисленные точки в многогранниках: геометрия, теория чисел, теория представлений, алгебра, оптимизация, статистика (PDF) , Современная математика, 452 , Провиденс, Род-Айленд: Американское математическое общество, DOI : 10.1090 / conm / 452 , ISBN 978-0-8218-4173-0, Руководство по ремонту 2416261