检索结果-内蒙古大学图书馆

Constructing Embedded lattice-Based algorithms for Multivariate Function Approximation with a Composite Number of Points

引用

CONSTRUCTIVE APPROXIMATION 2025年第1期61卷 81-113页

作者： Kuo, Frances Y. Mo, Weiwen Nuyens, Dirk UNSW Sydney Sch Math & Stat Sydney NSW 2052 Australia Dept Comp Sci KU Leuven Celestijnenlaan 200A B-3001 Leuven Belgium

We approximate d-variate periodic functions in weighted Korobov spaces with general weight parameters using n function values at lattice points. We do not limit n to be a prime number, as in currently available literature, but allow any number of points, including powers of 2, thus providing the fundamental theory for construction of embedded lattice sequences. Our results are constructive in that we provide a component-by-component algorithm which constructs a suitable generating vector for a given number of points or even a range of numbers of points. It does so without needing to construct the index set on which the functions will be represented. The resulting generating vector can then be used to approximate functions in the underlying weighted Korobov space. We analyse the approximation error in the worst-case setting under both the L2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2$$\end{document} and L infinity\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{\infty }$$\end{document} norms. Our component-by-component construction under the L2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2$$\end{document} norm achieves the best possible rate of convergence for lattice-based algorithms, and the theory can be applied to lattice-based kernel methods and splines. Depending on the value of the smoothness parameter alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackag

关键词： lattice rules lattice algorithms Embedded lattice sequences Multivariate function approximation Component-by-component construction Composite number of points Non-prime number of points

来源：评论

学校读者我要写书评

暂无评论

A quantum lattice algorithm with fourth-order accuracy for the one-dimensional Dirac equation

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2025年 533卷

作者： Dellar, Paul J. Univ Oxford Math Inst Radcliffe Observ Quarter Oxford OX2 6GG England

The discrete time quantum walk is a quantum cellular automaton whose wavefunction comprises pairs of complex numbers assigned to uniformly spaced points on a line. The wavefunction evolves through the application of an alternating sequence of unitary operators: streaming of wavefunction values to adjacent points, and a Hadamard-type unitary matrix to blend pairs of values at individual points. Each operator generates the exact evolution due to part of the Hamiltonian for the one-dimensional Dirac equation over a finite time step. Composing these operators thus creates a discrete approximation to the Dirac equation. However, the composition of two non-commuting operators creates a global splitting error proportional to the length of the time step. The global error can be reduced from first order to second order in the time step by a unitary pre-and post-processing of the initial conditions and final output. The algorithm then becomes equivalent to a symmetric composition, a Strang splitting, between the two operators. This paper describes a fourth-order accurate composition scheme using nine stages, the fewest possible when the lengths of the time steps employed in the different stages are constrained to be integer multiples of some base time step. Each stage is itself a symmetric composition between two operators. This fourth-order scheme produces quantitatively smaller errors for a typical benchmark problem on spatial lattices with 1024 or more points, and shows the expected fourth-order convergence on sufficiently fine lattices. It has greater accuracy, over sufficiently long times, than three better-known fourth-order composition schemes using fewer stages, but with lengths related by irrational coefficients. The truncation error for plane-wave solutions is due to an operator that separates into a resonant part proportional to the Hamiltonian, and a non-resonant part orthogonal to the Hamiltonian. The resonant part commutes with the exact evolution operator, so i

关键词： lattice algorithms Splitting algorithms Composition schemes Discrete invariants Resonant interactions

来源：评论

学校读者我要写书评

暂无评论

ECONOMICAL CONVEX COVERINGS AND APPLICATIONS

引用

SIAM JOURNAL ON COMPUTING 2024年第4期53卷 1002-1038页

作者： Arya, Sunil da Fonseca, Guilherme D. Mount, David M. Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Aix Marseille Univ Marseille France LIS Lab Marseille France Univ Maryland Dept Comp Sci College Pk MD USA Univ Maryland Inst Adv Comp Studies College Pk MD USA

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and epsilon > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an epsilon expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and epsilon-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the closest vector problem (CVP). It is known how to construct coverings of size nO(n)/epsilon (n 1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the l p unit ball, this bound has been improved to 2O(n)/epsilon(n 1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter epsilon > 0, we show that there exists a polytope P consisting of 2O(n)/epsilon (n 1)/2 vertices (facets) such that K subset of P subset of K(1+epsilon). This bound is optimal in the worst case up to factors of 2O(n). (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest (1 + epsilon)-approximate CVP algorithm that works in any norm, with a running time of 2O(n)/epsilon (n 1)/2 up to polynomial factors in the input size, and we obtain the fastest (1 + epsilon)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors o

关键词： approximation algorithms high dimensional geometry convex coverings Banach- Mazur metric lattice algorithms closest vector problem

来源：评论

学校读者我要写书评

暂无评论

Experimental Analysis of Integer Factorization Methods Using lattices 1

引用

19th International Workshop on Security on Advances in Information and Computer Security (IWSEC)

作者： Sato, Arata Auzemery, Aurelien Katayama, Akira Yasuda, Masaya Rikkyo Univ Tokyo Japan Univ Limoges Limoges France

ISBN: (数字)9789819777372

ISBN: (纸本)9789819777365;9789819777372

Since 1991, Schnorr has proposed methods using lattices for solving the integer factorization problem whose hardness supports the security of the RSA cryptosystem. In 2022, Yan et al. proposed a modification of Schnorr's lattices and reported numerical experiments by an optimization method using quantum computation. After that, Yamaguchi et al. reported that they succeeded in factoring RSA-type composite numbers of at most 55 bits based on Yan et al.'s modification, using classical annealing calculation. In this paper, we report experimental results of integer factorization methods using lattices in classical computing. Specifically, we analyze the structure of Schnorr's lattices to select suitable parameters and apply existing lattice algorithms for finding smooth relations in the difference-of-squares method. We report the running time of integer factorization using lattices for RSA-type composite numbers of at most 90 bits and the success probability of finding a smooth relation from a lattice. We also discuss the time complexity of integer factorization methods using lattices based on experimental results.

关键词： integer factorization lattice problems lattice algorithms

来源：评论

学校读者我要写书评

暂无评论

Economical Convex Coverings and Applications 34

Economical Convex Coverings and Applications

引用

34th ACM-SIAM Annual Symposium on Discrete algorithms (SODA)

作者： Arya, Sunil da Fonseca, Guilherme D. Mount, David M. Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Aix Marseille Univ Marseille France LIS Lab Marseille France Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

ISBN: (纸本)9781611977554

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and epsilon > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an epsilon expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and epsilon-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size n(O(n))/epsilon((n-1)2) for general convex bodies in R-n. In special cases, such as when the convex body is the l(p) unit ball, this bound has been improved to 2O(n)/epsilon((n-1)/2). This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. Given a wellcentered convex body K and an approximation parameter epsilon > 0, we show that there exists a polytope P consisting of 2(O(n))/epsilon((n-1)/2) vertices (facets) such that K subset of P subset of K(1 + epsilon). This bound is optimal in the worst case up to factors of 2(O(n)). (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest (1 + epsilon)-approximate CVP algorithm that works in any norm, with a running time of 2(O(n)/epsilon(n-1)/2) up to polynomial factors in the input size, and we obtain the fastest (1 + epsilon)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up

关键词： Approximation algorithms high dimensional geometry Banach-Mazur metric lattice algorithms closest vector problem Macbeath regions

来源：评论

学校读者我要写书评

暂无评论

Approximate CVP in Time 2^0.802n - Now in Any Norm! 23rd

Approximate CVP in Time 2<SUP>0.802n</SUP> - Now in Any Norm...

引用

23rd International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Rothvoss, Thomas Venzin, Moritz Univ Washington Seattle WA 98195 USA Ecole Polytech Fed Lausanne EPFL Lausanne Switzerland

ISBN: (纸本)9783031069017;9783031069000

We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time 2(0.802 n). This contrasts the corresponding 2(n) time, (gap)-SETH based lower bounds for these problems that even apply for small constant approximation. For both problems, SVP and CVP, we reduce to the case of the Euclidean norm. A key technical ingredient in that reduction is a twist of Milman's construction of an M-ellipsoid which approximates any symmetric convex body K with an ellipsoid E so that 2(epsilon n) translates of a constant scaling of E can cover K and vice versa.

关键词： lattice algorithms Sieving Integer programming

来源：评论

学校读者我要写书评

暂无评论

Computing Distributed Knowledge as the Greatest Lower Bound of Knowledge 19th

Computing Distributed Knowledge as the Greatest Lower Bound ...

引用

19th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS)

作者： Pinzon, Carlos Quintero, Santiago Ramirez, Sergio Valencia, Frank Ecole Polytech Paris CNRS LIX Palaiseau France Pontificia Univ Javeriana Cali Cali Colombia Ecole Polytech Paris LIX Palaiseau France INRIA Saclay Palaiseau France

ISBN: (纸本)9783030887018;9783030887001

Let L be a distributive lattice and E(L) be the set of join endomorphisms of L. We consider the problem of finding f Pi(E(L)) g given L and f, g is an element of E(L) as inputs. (1) We show that it can be solved in time O(n) where n = vertical bar L vertical bar. The previous upper bound was O(n(2)). (2) We characterize the standard notion of distributed knowledge of a group as the greatest lower bound of the join-endomorphisms representing the knowledge of each member of the group. (3) We show that deciding whether an agent has the distributed knowledge of two other agents can be computed in time O(n(2)) where n is the size of the underlying set of states. (4) For the special case of S5 knowledge, we show that it can be decided in time O(n alpha(n)) where alpha(n) is the inverse of the Ackermann function.

关键词： Distributive knowledge Join-endomorphims lattice algorithms

来源：评论

学校读者我要写书评

暂无评论

lattice-Filter-Based Multivariate Autoregressive Spectral Estimation With Joint Model Order and Estimation Bandwidth Adaptation

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第12期64卷 4968-4981页

作者： Niedzwiecki, Maciej Meller, Michal Chojnacki, Damian Gdansk Univ Technol Dept Automat Control Fac Elect Telecommun & Comp Sci PL-80233 Gdansk Poland

The problem of parametric autoregressive model-based estimation of a time-varying spectral density function of a multivariate nonstationary process is considered. It is shown that estimation results can be considerably improved if identification of the autoregressive model is carried out using the two-sided doubly exponentially weighted lattice algorithm, which combines results yielded by two one-sided lattice algorithms running forward in time and backward in time, respectively. It is also shown that the model order and the most appropriate estimation bandwidth can be efficiently selected using the suitably modified Akaikes final prediction error criterion.

关键词： Estimation Reactive power Autoregressive processes lattices Adaptation models Density functional theory Spectral analysis Identification of nonstationary systems lattice algorithms parametric spectrum estimation

来源：评论

学校读者我要写书评

暂无评论

Counting and Computing Join-Endomorphisms in lattices 1

引用

18th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS)

作者： Quintero, Santiago Ramirez, Sergio Rueda, Camilo Valencia, Frank Pontificia Univ Javeriana Cali Cali Colombia Ecole Polytech Paris LIX Palaiseau France Ecole Polytech Paris CNRS LIX Palaiseau France

ISBN: (数字)9783030435202

ISBN: (纸本)9783030435202;9783030435196

Structures involving a lattice and join-endomorphisms on it are ubiquitous in computer science. We study the cardinality of the set E(L) of all join-endomorphisms of a given finite lattice L. In particular, we show that when L is M-n, the discrete order of n elements extended with top and bottom, vertical bar E(L)vertical bar = n!L-n(-1) + (n + 1)(2) where L-n(x) is the Laguerre polynomial of degree n. We also study the following problem: Given a lattice L of size n and a set S subset of E(L) of size m, find the greatest lower bound Pi S-E(L). The join-endomorphism Pi(E(L)) S has meaningful interpretations in epistemic logic, distributed systems, and Aumann structures. We show that this problem can be solved with worst-case time complexity in O(n + m log n) for powerset lattices, O(mn(2)) for lattices of sets, and O(mn + n(3)) for arbitrary lattices. The complexity is expressed in terms of the basic binary lattice operations performed by the algorithm.

关键词： Join-endomorphisms lattice cardinality lattice algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing a lattice Basis Revisited 19

Computing a Lattice Basis Revisited

引用

44th ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Li, Jianwei Nguyen, Phong Q. NUS CQT Singapore Singapore Chinese Acad Sci AMSS KLMM Beijing Peoples R China Inria Paris France Univ Tokyo JFLI CNRS Tokyo Japan

ISBN: (纸本)9781450360845

Given (a, b) is an element of Z(2), Euclid's algorithm outputs the generator gcd(a, b) of the ideal aZ+ bZ. Computing a lattice basis is a high-dimensional generalization: given a(1), ... , a(n) is an element of Z(m), find a Z-basis of the lattice L = {Sigma(n)(i=1) x(i)a(i), x(i) is an element of Z} generated by the a(i)'s. The fastest algorithms known are HNF algorithms, but are not adapted to all applications, such as when the output should not be much longer than the input. We present an algorithm which extracts such a short basis within the same time as an HNF, by reduction to HNF. We also present an HNF-less algorithm, which reduces to Euclid's extended algorithm and can be generalized to quadratic forms. Both algorithms can extend primitive sets into bases.

关键词： lattice algorithms Z-basis HNF XGCD Integer quadratic forms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：