볼록 다면체의 정수점

Integer points in convex polyhedra
빨간색 점은 파란색 다각형 내의 정수 격자점이며, 후자는 2차원 선형 프로그램을 나타낸다.

볼록 다면체의[1] 정수 점의 연구는 "비음수 정수 값 해법이 몇 개의 비음수 계수를 가진 선형 방정식을 가진 시스템을 가지고 있는가" 또는 "정수 선형 프로그램이 몇 개의 해답을 가지고 있는가"와 같은 질문들에 의해 동기가 부여된다.다면체나 그것들에 관한 다른 질문들에 정수점을 세는 것은 표현 이론, 정류 대수학, 대수 기하학, 통계학, 컴퓨터 과학에서 발생한다.[2]

다면체에서 부착 격자의 정수점 집합 또는 더 일반적으로, 정수 번호 집합에 대한 수학 표기법 또는 Z에서 [3]Z-폴리헤드론이라고 한다.[4]

특성.

격자 Ⅱ의 경우, 민코프스키의 정리는 대칭 볼록 세트 S의 부피와 S에 포함된 격자 포인트의 수를 연관시킨다.

모든 정점이 격자의 요소인 폴리토프에 포함된 격자 점의 수는 폴리토프의 Ehrart 다항식으로 설명된다.이 다항식의 일부 계수에 대한 공식은 d(DRU)도 포함한다.

적용들

루프 최적화

루프 최적화에 대한 특정 접근방식에서 루프 본체의 실행 세트는 루프 제약조건에 의해 정의된 다면체의 정수점 세트로 간주된다.

참고 항목

참조 및 참고 사항

  1. ^ 어떤 맥락에서 볼록한 다면체를 단순히 "폴리헤드라"라고 부른다.
  2. ^ 다면체의 정수 점. 기하학, 수 이론, 표현 이론, 대수학, 최적화, 통계학, ACM--SIAM 공동 하계 연구 회의, 2006
  3. ^ "Z-폴리시론"이라는 용어는 또한 아핀 격자 안에 미세하게 많은 점의 볼록 선체인 볼록 격자 폴리토프의 동의어로 사용된다.
  4. ^ "복제된 공간에 대한 컴퓨터"의 내용:컴파일러 설계 핸드북:최적화 및 기계 코드 생성, CRC Press 2007, 제2판, ISBN1-4200-4382-X, 페이지 15-7

추가 읽기