Generator Matrices by Solving Integer Linear Programs

Loïs Paulin; David Coeurjolly; Nicolas Bonneel; Jean Claude Iehl; Victor Ostromoukhov; Alexander Keller

doi:10.1007/978-3-031-59762-6_26

Generator Matrices by Solving Integer Linear Programs

Loïs Paulin
, David Coeurjolly
, Nicolas Bonneel
, Jean Claude Iehl
, Victor Ostromoukhov
, Alexander Keller

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In quasi-Monte Carlo methods, generating high-dimensional low discrepancy sequences by generator matrices is a popular and efficient approach. Historically, constructing or finding such generator matrices has been a hard problem. In particular, it is challenging to take advantage of the intrinsic structure of a given numerical problem to design samplers of low discrepancy in certain subsets of dimensions. To address this issue, we devise a greedy algorithm allowing us to translate desired net properties into linear constraints on the generator matrix entries. Solving the resulting integer linear program yields generator matrices that satisfy the desired net properties. We demonstrate that our method finds generator matrices in challenging settings, offering low discrepancy sequences beyond the limitations of classic constructions.

Original language	English
Title of host publication	Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2022
Editors	Aicke Hinrichs, Friedrich Pillichshammer, Peter Kritzer
Publisher	Springer
Pages	525-541
Number of pages	17
ISBN (Print)	9783031597619
DOIs	https://doi.org/10.1007/978-3-031-59762-6_26
Publication status	Published - 1 Jan 2024
Externally published	Yes
Event	15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2022 - Linz, Austria Duration: 17 Jul 2022 → 22 Jul 2022

Publication series

Name	Springer Proceedings in Mathematics and Statistics
Volume	460
ISSN (Print)	2194-1009
ISSN (Electronic)	2194-1017

Conference

Conference	15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2022
Country/Territory	Austria
City	Linz
Period	17/07/22 → 22/07/22

Keywords

Digital (t, m, s)-nets and (t, s)-sequences
Generator matrices
Integer linear programs
Low discrepancy sequences
Optimization
Quasi-Monte Carlo methods

Access to Document

10.1007/978-3-031-59762-6_26

Cite this

Paulin, L., Coeurjolly, D., Bonneel, N., Iehl, J. C., Ostromoukhov, V., & Keller, A. (2024). Generator Matrices by Solving Integer Linear Programs. In A. Hinrichs, F. Pillichshammer, & P. Kritzer (Eds.), Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2022 (pp. 525-541). (Springer Proceedings in Mathematics and Statistics; Vol. 460). Springer. https://doi.org/10.1007/978-3-031-59762-6_26

@inproceedings{970c843c0a454f3caafb5203a9b37cac,

title = "Generator Matrices by Solving Integer Linear Programs",

abstract = "In quasi-Monte Carlo methods, generating high-dimensional low discrepancy sequences by generator matrices is a popular and efficient approach. Historically, constructing or finding such generator matrices has been a hard problem. In particular, it is challenging to take advantage of the intrinsic structure of a given numerical problem to design samplers of low discrepancy in certain subsets of dimensions. To address this issue, we devise a greedy algorithm allowing us to translate desired net properties into linear constraints on the generator matrix entries. Solving the resulting integer linear program yields generator matrices that satisfy the desired net properties. We demonstrate that our method finds generator matrices in challenging settings, offering low discrepancy sequences beyond the limitations of classic constructions.",

keywords = "Digital (t, m, s)-nets and (t, s)-sequences, Generator matrices, Integer linear programs, Low discrepancy sequences, Optimization, Quasi-Monte Carlo methods",

author = "Lo{\"i}s Paulin and David Coeurjolly and Nicolas Bonneel and Iehl, \{Jean Claude\} and Victor Ostromoukhov and Alexander Keller",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2022 ; Conference date: 17-07-2022 Through 22-07-2022",

year = "2024",

month = jan,

day = "1",

doi = "10.1007/978-3-031-59762-6\_26",

language = "English",

isbn = "9783031597619",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer",

pages = "525--541",

editor = "Aicke Hinrichs and Friedrich Pillichshammer and Peter Kritzer",

booktitle = "Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2022",

}

Paulin, L, Coeurjolly, D, Bonneel, N, Iehl, JC, Ostromoukhov, V & Keller, A 2024, Generator Matrices by Solving Integer Linear Programs. in A Hinrichs, F Pillichshammer & P Kritzer (eds), Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2022. Springer Proceedings in Mathematics and Statistics, vol. 460, Springer, pp. 525-541, 15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2022, Linz, Austria, 17/07/22. https://doi.org/10.1007/978-3-031-59762-6_26

Generator Matrices by Solving Integer Linear Programs. / Paulin, Loïs; Coeurjolly, David; Bonneel, Nicolas et al.
Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2022. ed. / Aicke Hinrichs; Friedrich Pillichshammer; Peter Kritzer. Springer, 2024. p. 525-541 (Springer Proceedings in Mathematics and Statistics; Vol. 460).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Generator Matrices by Solving Integer Linear Programs

AU - Paulin, Loïs

AU - Coeurjolly, David

AU - Bonneel, Nicolas

AU - Iehl, Jean Claude

AU - Ostromoukhov, Victor

AU - Keller, Alexander

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024/1/1

Y1 - 2024/1/1

N2 - In quasi-Monte Carlo methods, generating high-dimensional low discrepancy sequences by generator matrices is a popular and efficient approach. Historically, constructing or finding such generator matrices has been a hard problem. In particular, it is challenging to take advantage of the intrinsic structure of a given numerical problem to design samplers of low discrepancy in certain subsets of dimensions. To address this issue, we devise a greedy algorithm allowing us to translate desired net properties into linear constraints on the generator matrix entries. Solving the resulting integer linear program yields generator matrices that satisfy the desired net properties. We demonstrate that our method finds generator matrices in challenging settings, offering low discrepancy sequences beyond the limitations of classic constructions.

AB - In quasi-Monte Carlo methods, generating high-dimensional low discrepancy sequences by generator matrices is a popular and efficient approach. Historically, constructing or finding such generator matrices has been a hard problem. In particular, it is challenging to take advantage of the intrinsic structure of a given numerical problem to design samplers of low discrepancy in certain subsets of dimensions. To address this issue, we devise a greedy algorithm allowing us to translate desired net properties into linear constraints on the generator matrix entries. Solving the resulting integer linear program yields generator matrices that satisfy the desired net properties. We demonstrate that our method finds generator matrices in challenging settings, offering low discrepancy sequences beyond the limitations of classic constructions.

KW - Digital (t, m, s)-nets and (t, s)-sequences

KW - Generator matrices

KW - Integer linear programs

KW - Low discrepancy sequences

KW - Optimization

KW - Quasi-Monte Carlo methods

U2 - 10.1007/978-3-031-59762-6_26

DO - 10.1007/978-3-031-59762-6_26

M3 - Conference contribution

AN - SCOPUS:85200685047

SN - 9783031597619

T3 - Springer Proceedings in Mathematics and Statistics

SP - 525

EP - 541

BT - Monte Carlo and Quasi-Monte Carlo Methods - MCQMC 2022

A2 - Hinrichs, Aicke

A2 - Pillichshammer, Friedrich

A2 - Kritzer, Peter

PB - Springer

T2 - 15th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2022

Y2 - 17 July 2022 through 22 July 2022

ER -