{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T03:08:03Z","timestamp":1775099283421,"version":"3.50.1"},"reference-count":13,"publisher":"American Mathematical Society (AMS)","issue":"254","license":[{"start":{"date-parts":[[2007,1,4]],"date-time":"2007-01-04T00:00:00Z","timestamp":1167868800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>We reformulate the original component-by-component algorithm for rank-<inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"1\">\n  <mml:semantics>\n    <mml:mn>1<\/mml:mn>\n    <mml:annotation encoding=\"application\/x-tex\">1<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> lattices in a matrix-vector notation so as to highlight its structural properties. For function spaces similar to a weighted Korobov space, we derive a technique which has construction cost <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis s n log left-parenthesis n right-parenthesis right-parenthesis\">\n  <mml:semantics>\n    <mml:mrow>\n      <mml:mi>O<\/mml:mi>\n      <mml:mo stretchy=\"false\">(<\/mml:mo>\n      <mml:mi>s<\/mml:mi>\n      <mml:mi>n<\/mml:mi>\n      <mml:mi>log<\/mml:mi>\n      <mml:mo>\u2061<\/mml:mo>\n      <mml:mo stretchy=\"false\">(<\/mml:mo>\n      <mml:mi>n<\/mml:mi>\n      <mml:mo stretchy=\"false\">)<\/mml:mo>\n      <mml:mo stretchy=\"false\">)<\/mml:mo>\n    <\/mml:mrow>\n    <mml:annotation encoding=\"application\/x-tex\">O(s n \\log (n))<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>, in contrast with the original algorithm which has construction cost <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis s n squared right-parenthesis\">\n  <mml:semantics>\n    <mml:mrow>\n      <mml:mi>O<\/mml:mi>\n      <mml:mo stretchy=\"false\">(<\/mml:mo>\n      <mml:mi>s<\/mml:mi>\n      <mml:msup>\n        <mml:mi>n<\/mml:mi>\n        <mml:mn>2<\/mml:mn>\n      <\/mml:msup>\n      <mml:mo stretchy=\"false\">)<\/mml:mo>\n    <\/mml:mrow>\n    <mml:annotation encoding=\"application\/x-tex\">O(s n^2)<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>. Herein <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"s\">\n  <mml:semantics>\n    <mml:mi>s<\/mml:mi>\n    <mml:annotation encoding=\"application\/x-tex\">s<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> is the number of dimensions and <inline-formula content-type=\"math\/mathml\">\n<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n  <mml:semantics>\n    <mml:mi>n<\/mml:mi>\n    <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n  <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> the number of points (taken prime). In contrast to other approaches to speed up construction, our fast algorithm computes exactly the same quantity as the original algorithm. The presented algorithm can also be used to construct randomly shifted lattice rules in weighted Sobolev spaces.<\/p>","DOI":"10.1090\/s0025-5718-06-01785-6","type":"journal-article","created":{"date-parts":[[2006,2,15]],"date-time":"2006-02-15T16:05:20Z","timestamp":1140019520000},"page":"903-920","source":"Crossref","is-referenced-by-count":179,"title":["Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces"],"prefix":"10.1090","volume":"75","author":[{"given":"Dirk","family":"Nuyens","sequence":"first","affiliation":[]},{"given":"Ronald","family":"Cools","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2006,1,4]]},"reference":[{"key":"1","series-title":"National Bureau of Standards Applied Mathematics Series, No. 55","volume-title":"Handbook of mathematical functions with formulas, graphs, and mathematical tables","author":"Abramowitz, Milton","year":"1964"},{"key":"2","first-page":"181","article-title":"Constructing good lattice rules with millions of points","author":"Dick, Josef","year":"2004"},{"issue":"248","key":"3","doi-asserted-by":"publisher","first-page":"1967","DOI":"10.1090\/S0025-5718-03-01610-7","article-title":"Reducing the construction cost of the component-by-component construction of good lattice rules","volume":"73","author":"Dick, J.","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"5","key":"4","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.jco.2003.06.002","article-title":"Liberating the weights","volume":"20","author":"Dick, Josef","year":"2004","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"5","unstructured":"Matteo Frigo and Steven G. Johnson, FFTW: An adaptive software architecture for the FFT, Proc. 1998 IEEE Intl. Conf. Acoustics Speech and Signal Processing, Vol. 3, IEEE, 1998, pp. 1381\u20131384."},{"key":"6","series-title":"Johns Hopkins Studies in the Mathematical Sciences","isbn-type":"print","volume-title":"Matrix computations","author":"Golub, Gene H.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/080185413X","edition":"3"},{"key":"7","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-1-4612-1702-2_3","article-title":"Lattice rules: how well do they measure up?","author":"Hickernell, Fred J.","year":"1998"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0885-064X(03)00006-2","article-title":"Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces","volume":"19","author":"Kuo, F. Y.","year":"2003","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"9","unstructured":"Dirk Nuyens and Ronald Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces, Report TW392, Dept. of Computer Science, K.U.Leuven, May 2004."},{"key":"10","doi-asserted-by":"crossref","unstructured":"Charles M. Rader, Discrete Fourier transforms when the number of data samples is prime, Proc. IEEE 5 (1968), 1107\u20131108.","DOI":"10.1109\/PROC.1968.6477"},{"issue":"5","key":"11","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1137\/S0036142901393942","article-title":"Constructing randomly shifted lattice rules in weighted Sobolev spaces","volume":"40","author":"Sloan, I. H.","year":"2002","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"237","key":"12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1090\/S0025-5718-01-01342-4","article-title":"Component-by-component construction of good lattice rules","volume":"71","author":"Sloan, I. H.","year":"2002","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"13","series-title":"Frontiers in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970999","volume-title":"Computational frameworks for the fast Fourier transform","volume":"10","author":"Van Loan, Charles","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712858"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01785-6\/S0025-5718-06-01785-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01785-6\/S0025-5718-06-01785-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T02:17:04Z","timestamp":1627611424000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01785-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,4]]},"references-count":13,"journal-issue":{"issue":"254","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["S0025-5718-06-01785-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01785-6","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1,4]]}}}