research-article

Algorithm 958: Lattice Builder: A General Software Tool for Constructing Rank-1 Lattice Rules

Authors:

Pierre L'ecuyer,

David MungerAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 42, Issue 2

Article No.: 15, Pages 1 - 30

https://doi.org/10.1145/2754929

Published: 24 May 2016 Publication History

Get Access

Abstract

We introduce a new software tool and library named Lattice Builder, written in C++, that implements a variety of construction algorithms for good rank-1 lattice rules. It supports exhaustive and random searches, as well as component-by-component (CBC) and random CBC constructions, for any number of points, and for various measures of (non)uniformity of the points. The measures currently implemented are all shift-invariant and represent the worst-case integration error for certain classes of integrands. They include, for example, the weighted Pα square discrepancy, the Rα criterion, and figures of merit based on the spectral test, with projection-dependent weights. Each of these measures can be computed as a finite sum. For the Pα and Rα criteria, efficient specializations of the CBC algorithm are provided for projection-dependent, order-dependent, and product weights. For numbers of points that are integer powers of a prime base, the construction of embedded rank-1 lattice rules is supported through any of these algorithms, and through a fast CBC algorithm, with a variety of possibilities for the normalization of the merit values of individual embedded levels and for their combination into a single merit value. The library is extensible, thanks to the decomposition of the algorithms into decoupled components, which makes it easy to implement new types of weights, new search domains, new figures of merit, and so on.

Supplementary Material

ZIP File (958.zip)

Software for Lattice Builder: A General Software Tool for Constructing Rank-1 Lattice Rules

Download
14.43 MB

References

[1]

A. Alexandrescu. 2001. Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley Longman Publishing Co., Inc., Boston, MA.

Digital Library

Google Scholar

[2]

Boost.org. 2012. Boost C++ libraries. Retrieved April 8, 2016 from http://www.boost.org.

Google Scholar

[3]

J. Burkardt. 2012. LATTICE_RULE. Retrieved April 8, 2016 from http://people.sc.fsu.edu/&sim;jburkardt/m_src/lattice_rule/lattice_rule.html.

Google Scholar

[4]

J. H. Conway and N. J. A. Sloane. 1999. Sphere Packings, Lattices and Groups (3rd ed.). Grundlehren der Mathematischen Wissenschaften 290. Springer-Verlag, New York, NY.

Google Scholar

[5]

R. Cools, F. Y. Kuo, and D. Nuyens. 2006. Constructing embedded lattice rules for multivariate integration. SIAM Journal on Scientific Computing 28, 16, 2162--2188.

Digital Library

Google Scholar

[6]

J. Coplien. 1995. Curiously recurring template pattern. C++ Report 24--27.

Crossref

Google Scholar

[7]

R. Cranley and T. N. L. Patterson. 1976. Randomization of number theoretic methods for multiple integration. SIAM Journal on Numerical Analysis 13, 6, 904--914.

Crossref

Google Scholar

[8]

J. Dick and F. Pillichshammer. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge, U.K.

Digital Library

Google Scholar

[9]

J. Dick, F. Pillichshammer, and B. J. Waterhouse. 2008. The construction of good extensible rank-1 lattices. Mathematics of Computation 77, 264, 2345--2373.

Google Scholar

[10]

J. Dick, I. H. Sloan, X. Wang, and H. Woźniakowski. 2004. Liberating the weights. Journal of Complexity20, 5, 593--623.

Digital Library

Google Scholar

[11]

J. Dick, I. H. Sloan, X. Wang, and H. Woźniakowski. 2006. Good lattice rules in weighted Korobov spaces with general weights. Numerische Mathematik 103, 63--97.

Digital Library

Google Scholar

[12]

B. Efron and C. Stein. 1981. The jackknife estimator of variance. Annals of Statistics 9, 586--596.

Crossref

Google Scholar

[13]

M. Frigo and S. G. Johnson. 2005. The design and implementation of FFTW3. Proceedings of the IEEE 93, 2, 216--231. Special issue on “Program Generation, Optimization, and Platform Adaptation.”

Crossref

Google Scholar

[14]

F. J. Hickernell. 1998a. A generalized discrepancy and quadrature error bound. Mathematics of Computation 67, 221, 299--322.

Digital Library

Google Scholar

[15]

F. J. Hickernell. 1998b. Lattice rules: How well do they measure up? In Random and Quasi-Random Point Sets, P. Hellekalek and G. Larcher, (Eds.). Lecture Notes in Statistics Series, Vol. 138. Springer-Verlag, New York, 109--166.

Google Scholar

[16]

F. J. Hickernell, H. S. Hong, P. L’Ecuyer, and C. Lemieux. 2001. Extensible lattice sequences for quasi-Monte Carlo quadrature. SIAM Journal on Scientific Computing 22, 3, 1117--1138.

Digital Library

Google Scholar

[17]

F. J. Hickernell and H. Niederreiter. 2003. The existence of good extensible rank-1 lattices. Journal of Complexity 19, 3, 286--300.

Digital Library

Google Scholar

[18]

D. E. Knuth. 1998. The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley, Reading, MA.

Digital Library

Google Scholar

[19]

F. Kuo. 2012. Lattice rule generating vectors. Retrieved April 8, 2016 from http://web.maths.unsw.edu.au/ fkuo/lattice/index.html.

Google Scholar

[20]

F. Y. Kuo and S. Joe. 2002. Component-by-component construction of good lattice rules with a composite number of points. Journal of Complexity 18, 4, 943--976.

Digital Library

Google Scholar

[21]

F. Y. Kuo, C. Schwab, and I. H. Sloan. 2011. Quasi-Monte Carlo methods for high dimensional integration: The standard (weighted Hilbert space) setting and beyond. The ANZIAM Journal 53, 1--37.

Crossref

Google Scholar

[22]

F. Y. Kuo, C. Schwab, and I. H. Sloan. 2012. Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients. SIAM Journal on Numerical Analysis 50, 3351--3374.

Crossref

Google Scholar

[23]

F. Y. Kuo, I. H. Sloan, and H. Woźniakowski. 2008. Lattice rule algorithms for multivariate approximation in the average case setting. Journal of Complexity 24, 283--323.

Digital Library

Google Scholar

[24]

F. Y. Kuo, G. W. Wasilkowski, and B. J. Waterhouse. 2006. Randomly shifted lattice rules for unbounded integrands. Journal of Complexity 22, 5, 630--651.

Digital Library

Google Scholar

[25]

P. L’Ecuyer. 1999a. Tables of linear congruential generators of different sizes and good lattice structure. Mathematics of Computation 68, 225, 249--260.

Digital Library

Google Scholar

[26]

P. L’Ecuyer. 1999b. Tables of maximally equidistributed combined LFSR generators. Mathematics of Computation 68, 225, 261--269.

Digital Library

Google Scholar

[27]

P. L’Ecuyer. 2008. SSJ: A Java Library for Stochastic Simulation. Software user’s guide. Retrieved April 8, 2016 from http://www.iro.umontreal.ca/&sim;lecuyer.

Google Scholar

[28]

P. L’Ecuyer. 2009. Quasi-Monte Carlo methods with applications in finance. Finance and Stochastics 13, 3, 307--349.

Crossref

Google Scholar

[29]

P. L’Ecuyer and R. Couture. 1997. An implementation of the lattice and spectral tests for multiple recursive linear random number generators. INFORMS Journal on Computing 9, 2, 206--217.

Digital Library

Google Scholar

[30]

P. L’Ecuyer and C. Lemieux. 2000. Variance reduction via lattice rules. Management Science 46, 9, 1214--1235.

Digital Library

Google Scholar

[31]

P. L’Ecuyer and D. Munger. 2012. On figures of merit for randomly-shifted lattice rules. In Monte Carlo and Quasi-Monte Carlo Methods 2010, H. Woźniakowski and L. Plaskota, (Eds.). Springer-Verlag, Berlin, 133--159.

Google Scholar

[32]

P. L’Ecuyer and D. Munger. 2016. Lattice Builder Manual and Source Code. Retrieved May 9, 2016 from http://www.iro.umontreal.ca/&sim;lecuyer/ and https://github.com/umontreal-simul/.

Google Scholar

[33]

P. L’Ecuyer, D. Munger, and B. Tuffin. 2010. On the distribution of integration error by randomly-shifted lattice rules. Electronic Journal of Statistics 4, 950--993.

Crossref

Google Scholar

[34]

P. L’Ecuyer and A. B. Owen, (Eds.). 2009. Monte Carlo and Quasi-Monte Carlo Methods 2008. Springer-Verlag, Berlin.

Digital Library

Google Scholar

[35]

C. Lemieux. 2009. Monte Carlo and Quasi-Monte Carlo Sampling. Springer-Verlag, New York, NY.

Google Scholar

[36]

C. Lemieux. 2012. RandQMC library. Retrieved April 8, 2016 from http://www.math.uwaterloo.ca/&sim;clemieux/randqmc.html.

Google Scholar

[37]

R. Lischner. 2009. Exploring C++: The Programmer’s Introduction to C++. Apress, Springer.

Digital Library

Google Scholar

[38]

R. Liu and A. B. Owen. 2006. Estimating mean dimensionality of analysis of variance decompositions. Journal of the American Statistical Association 101, 474, 712--721.

Crossref

Google Scholar

[39]

D. Maisonneuve. 1972. Recherche et utilisation des “bons treillis”, programmation et résultats numériques. In Applications of Number Theory to Numerical Analysis, S. K. Zaremba, (Ed.). Academic Press, New York, NY, 121--201.

Google Scholar

[40]

H. Niederreiter. 1992a. New methods for pseudorandom number and pseudorandom vector generation. In Proceedings of the 1992 Winter Simulation Conference. IEEE Press, 264--269.

Digital Library

Google Scholar

[41]

H. Niederreiter. 1992b. Random Number Generation and Quasi-Monte Carlo Methods. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics Series, Vol. 63. SIAM, Philadelphia, PA.

Digital Library

Google Scholar

[42]

D. Nuyens. 2012. Fast component-by-component constructions. Retrieved April 8, 2016 from http://people.cs.kuleuven.be/&sim;dirk.nuyens/fast-cbc/.

Google Scholar

[43]

D. Nuyens. 2014. The construction of good lattice rules and polynomial lattice rules. In Uniform Distribution and Quasi-Monte Carlo Methods: Discrepancy, Integration and Applications, P. Kritzer, H. Niederreiter, F. Pillichshammer, and A. Winterhof (Eds.). De Gruyter, 223--255.

Google Scholar

[44]

D. Nuyens and R. Cools. 2006a. Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Mathematics of Computation 75, 903--920.

Crossref

Google Scholar

[45]

D. Nuyens and R. Cools. 2006b. Fast component-by-component construction, a reprise for different kernels. In Monte Carlo and Quasi-Monte Carlo Methods 2004, H. Niederreiter and D. Talay, (Eds.). 373--387.

Google Scholar

[46]

D. Nuyens and R. Cools. 2006c. Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points. Journal of Complexity 22, 4--28.

Digital Library

Google Scholar

[47]

A. B. Owen. 1998. Latin supercube sampling for very high-dimensional simulations. ACM Transactions on Modeling and Computer Simulation 8, 1, 71--102.

Digital Library

Google Scholar

[48]

V. Sinescu and P. L’Ecuyer. 2009. On the behavior of weighted star discrepancy bounds for shifted lattice rules. In Monte Carlo and Quasi-Monte Carlo Methods 2008, P. L’Ecuyer and A. B. Owen, (Eds.). Springer-Verlag, Berlin, 603--616.

Google Scholar

[49]

V. Sinescu and P. L’Ecuyer. 2012. Variance bounds and existence results for randomly shifted lattice rules. Journal of Computational and Applied Mathematics 236, 3296--3307.

Digital Library

Google Scholar

[50]

I. H. Sloan and S. Joe. 1994. Lattice Methods for Multiple Integration. Clarendon Press, Oxford. UK.

Google Scholar

[51]

I. H. Sloan and H. Woźniakowski. 1998. When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals. Journal of Complexity 14, 1--33.

Digital Library

Google Scholar

[52]

I. M. Sobol’. 2001. Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Mathematics and Computers in Simulation 55, 271--280.

Digital Library

Google Scholar

[53]

X. Wang. 2007. Constructing robust good lattice rules for computational finance. SIAM Journal on Scientific Computing 29, 2, 598--621.

Digital Library

Google Scholar

[54]

X. Wang and I. H. Sloan. 2006. Efficient weighted lattice rules with applications to finance. SIAM Journal on Scientific Computing 28, 2, 728--750.

Digital Library

Google Scholar

[55]

H. Woźniakowski and L. Plaskota, (Eds.). 2012. Monte Carlo and Quasi-Monte Carlo Methods 2010. Springer-Verlag, Berlin.

Google Scholar

Cited By

View all

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
L'Ecuyer PCherkanihassani YEl Amine Derkaoui M(2024)Pre-Scrambled Digital Nets for Randomized Quasi-Monte Carlo2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838945(443-454)Online publication date: 15-Dec-2024
https://doi.org/10.1109/WSC63780.2024.10838945
Paulin LCoeurjolly DBonneel NIehl JOstromoukhov VKeller A(2024)Generator Matrices by Solving Integer Linear ProgramsMonte Carlo and Quasi-Monte Carlo Methods10.1007/978-3-031-59762-6_26(525-541)Online publication date: 13-Jul-2024
https://doi.org/10.1007/978-3-031-59762-6_26
Show More Cited By

Index Terms

Algorithm 958: Lattice Builder: A General Software Tool for Constructing Rank-1 Lattice Rules
1. Mathematics of computing
  1. Mathematical software

Recommendations

The existence of good extensible rank-1 lattices

Extensible integration lattices have the attractive property that the number of points in the node set may be increased while retaining the existing points. It is shown here that there exist generating vectors, h, for extensible rank-1 lattices such ...
Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights

We study the problem of constructing shifted rank-1 lattice rules for the approximation of high-dimensional integrals with a low weighted star discrepancy, for classes of functions having bounded weighted variation, where the weighted variation is ...
Simulating option prices and sensitivities by higher rank lattice rules
MS'06: Proceedings of the 17th IASTED international conference on Modelling and simulation

In this paper we introduce the intermediate rank or higher rank lattice rule for the general case when the number of quadrature points is n^tm, where m is a composite integer, t is the rank of the rule, n is an integer such that (n,m) = 1. Our emphasis ...

Reviews

Reviewer: Sanzheng Qiao

The problem of numerically integrating multidimensional functions arises from function approximation, optimization, and solving partial differential equations, among others. The number of function evaluations, the major cost of numerical integration, required by quadrature rules such as Simpson's rule or the Gaussian quadrature rule, grows exponentially as the dimension increases. An alternative method is the Monte Carlo method, in which the integrand is evaluated at random points in the integration region. Obviously, a good random point generator is critical. It is known that multidimensional points with each component uniformly distributed in one dimension tend to appear in clusters, causing errors. This software tool, Lattice Builder, constructs good integration lattices for multidimensional numerical integration. To be precise, this tool uses rank-1 lattice rules to ensure that the points generated do not superpose on each other in lower-dimensional projections. Lattice rules are specific to applications. This software searches for the lattice rules suitable for a particular application by providing parameters. Good software should give the user a choice. The modular design of the software allows the user to use his or her own program to replace an existing component, for example, lattice type, traversal type, or weight type. The software provides three user interfaces: an application programming interface (API), a command-line interface (CLI), and a graphical user interface (GUI). The user can develop his or her modules through the API. This software is a first major step in building lattice rules. Further developments and contributions from users are necessary. This paper reports extensive experimental results. More interpretations of the results would be helpful. A user's guide that includes sample runs of typical problems would be useful. The documentation in the code needs to be improved. Well-documented code is essential for maintenance and user contributions. The software package can be downloaded from http://github.com/umontreal-simul. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 42, Issue 2

June 2016

156 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2936306

Editor:
Michael A. Heroux
Sandia National Laboratories, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 May 2016

Accepted: 01 March 2015

Revised: 01 October 2014

Received: 01 September 2012

Published in TOMS Volume 42, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
L'Ecuyer PCherkanihassani YEl Amine Derkaoui M(2024)Pre-Scrambled Digital Nets for Randomized Quasi-Monte Carlo2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838945(443-454)Online publication date: 15-Dec-2024
https://doi.org/10.1109/WSC63780.2024.10838945
Paulin LCoeurjolly DBonneel NIehl JOstromoukhov VKeller A(2024)Generator Matrices by Solving Integer Linear ProgramsMonte Carlo and Quasi-Monte Carlo Methods10.1007/978-3-031-59762-6_26(525-541)Online publication date: 13-Jul-2024
https://doi.org/10.1007/978-3-031-59762-6_26
L'Ecuyer PNakayama MOwen ATuffin B(2023)Confidence Intervals for Randomized Quasi-Monte Carlo EstimatorsProceedings of the Winter Simulation Conference10.5555/3643142.3643179(445-456)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3643142.3643179
Doignies BBonneel NCoeurjolly DDigne JPaulin LIehl JOstromoukhov V(2023)Example-Based Sampling with Diffusion ModelsSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618243(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618243
L’Ecuyer PNakayama MOwen ATuffin B(2023)Confidence Intervals for Randomized Quasi-Monte Carlo Estimators2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10408613(445-456)Online publication date: 10-Dec-2023
https://doi.org/10.1109/WSC60868.2023.10408613
de Doncker EYuasa FIshikawa T(2023)Numerical Regularization for 4-loop Self-Energy Feynman DiagramsJournal of Physics: Conference Series10.1088/1742-6596/2438/1/0121472438:1(012147)Online publication date: 1-Feb-2023
https://doi.org/10.1088/1742-6596/2438/1/012147
Thevenin SAdulyasak YCordeau J(2022)Stochastic Dual Dynamic Programming for Multiechelon Lot Sizing with Component SubstitutionINFORMS Journal on Computing10.1287/ijoc.2022.121534:6(3151-3169)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1215
L’Ecuyer PPuchhammer FBen Abdellah A(2022)Monte Carlo and Quasi–Monte Carlo Density Estimation via ConditioningINFORMS Journal on Computing10.1287/ijoc.2021.113534:3(1729-1748)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1135
Kim SDoh JHan J(2022)Modeling and rendering non-euclidean spaces approximated with concatenated polytopesACM Transactions on Graphics10.1145/3528223.353018641:4(1-13)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530186
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

Supplementary Material

References

Cited By

Index Terms

Recommendations

The existence of good extensible rank-1 lattices

Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights

Simulating option prices and sensitivities by higher rank lattice rules

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Badges

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations