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

EFFICIENT COVARIANCE LADDER algorithms FOR FINITE ARITHMETIC APPLICATIONS

SIGNAL PROCESSING 1987年第1期13卷 29-70页

作者： STROBACH, P SIEMENS AG Information Systems Laboratory ZT ZTI INF 121 D-8000 München 83 Fed. Rep. Germany

This paper is concerned with the problem of constructing numerically robust covariance ladder estimation algorithms for finite arithmetic applications. Conventional least-squares (LS) ladder algorithms suffer from mixed time and order recursive update equations resulting in a poor numerical accuracy when implemented with finite arithmetic. In this paper, a more ‘direct’ and numerically robust computation approach of the ladder update recursions using the most recently introduced algebraic method of generalized residual energies (GRE's) is presented. The new algorithms separate time and order recursions in two independent subalgorithms with a highly modular structure. Besides the general framework, five algorithms of this type are presented. Based on these algorithms, a VLSI ladder chip-set is proposed. Fixed-point simulations of the new VLSI structures are performed for several types of input data. The experimental analysis shows that the new algorithms are superior over conventional techniques and can operate at a multiplier wordlength as low as 8 bits. Dieser Aufsatz behandelt das Problem des Entwurfs numerisch robuster Kovarianz Ladder Algorithmen für die Anwendung in Echtzeitrechnern mit beschränkter numerischer Genauigkeit. Konventionelle Least-Squares (LS) Ladder Algorithmen basieren auf gemischt zeit- und ordnungsrekursiven Aktualisierungsgleichungen welche auf eine schlechte numerische Genauigkeit der Algorithmen führen. Eine erhebliche Verbesserung der numerischen Eigenschaften von Ladder Algorithmen läβt sich mit Hilfe der neuen algebraischen Methode der verallgemeinerten Residualenergien (GRE's) erreichen, welche in diesem Aufsatz vorgestellt wird. Die aus dem neuen Ansatz resultierenden Verfahren erlauben die Trennung von Zeit- und Ordnungsrekursionen in zwei unabhängige Teilalgorithmen mit höchst modularer Struktur. Neben der allgemeinen Herleitung werden insgesamt fünf numerisch robuste Ladder Algorithmen dieses Typs vorgestellt. Basierend auf diesen V

关键词： Autoregressive modeling ladder algorithms lattice algorithms VLSI realizations

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Pricing Discrete Asian Barrier Options on lattices

Pricing Discrete Asian Barrier Options on Lattices

引用

IEEE Conference on Computational Intelligence for Financial Engineering and Economics (CIFEr)

作者： Hsu, William W. Y. Lu, Cheng-Yu Kao, Ming-Yang Lyuu, Yuh-Dauh Ho, Jan-Ming Acad Sinica Inst Informat Sci Taipei Taiwan Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL USA Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei Taiwan

ISBN: (纸本)9781467318037

Asian barrier options are barrier options whose trigger is based on an average underlying price. They provide the advantages of both Asian options and barrier options. This paper introduces the first quadratic-time lattice algorithm to price European-style Asian barrier options. It is by far the most efficient lattice algorithm with convergence guarantees. The algorithm relies on the Lagrange multipliers to optimally distribute the number of states for each node of the multinomial lattice. We also show experiment results to demonstrate effectiveness and efficiency of our algorithm by comparing with Monte Carlo simulations.

关键词： Asian options barrier options multinomial model lattice algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Fourier Orthogonalization 16

Fast Fourier Orthogonalization

引用

41st ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Ducas, Leo Prest, Thomas CWI Cryptol Grp Amsterdam Netherlands Thales Commun & Secur Gennevilliers France

ISBN: (纸本)9781450343800

The classical fast Fourier transform (FFT) allows to compute in quasi -linear time the product of two polynomials, in the circular convolution ring R[x]I(x(d) - 1) - a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix -vector products when the matrix is circulant. In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of matrices with circulant blocks of size d x d. We show that, when d is composite, it is possible to proceed to the orthogonalization in an inductive way up to an appropriate re-indexation of rows and columns. This leads to a structured Gram -Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the nearest plane algorithm. The complexity of both algorithms may be brought down to circle minus(d log d). Our results easily extend to cyclotomic rings, and can be adapted to Gaussian samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.

关键词： Fast Fourier transform Gram-Schmidt orthogonalization nearest plane algorithm lattice algorithms lattice trapdoor functions

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

String Transformation Based Morphology Learning

引用

INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS 2019年第4期43卷 467-476页

作者： Kovacs, Laszlo Szabo, Gabor Univ Miskolc Inst Informat Technol H-3515 Miskolc Hungary

There are several morphological methods that can solve the morphological rule induction problem. For different languages this task represents different difficulty levels. In this paper we propose a novel method that can learn prefix, infix and suffix transformations as well. The test language is Hungarian (which is a morphologically complex Uralic language containing a high number of affix types and complex inflection rules), and we chose a previously generated word pair set of accusative case for evaluating the method, comparing its training time, memory requirements, average inflection time and correctness ratio with some of the most popular models like dictionaries, finite state transducers, the tree of aligned suffix rules and a lattice based method. We also provide multiple training and searching strategies, introducing parallelism and the concept of prefix trees to optimize the number of rules that need to be processed for each input word. This newly created novel method can be applied not only for morphology, but also for any problems in the field of bioinformatics and data mining that can benefit from string transformations learning.

关键词： machine learning natural language processing inflection rule induction agglutination dictionaries finite state transducers tree of aligned suffix rules lattice algorithms string transformations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：