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

arXiv 2020年

作者： Chowdhury, Agniva London, Palma Avron, Haim Drineas, Petros Department of Statistics Purdue University West LafayetteIN United States Department of Computer Science California Institute of Technology PasadenaCA United States School of Mathematical Sciences Tel Aviv University Tel Aviv Israel Department of Computer Science Purdue University West LafayetteIN United States

Linear programming (LP) is an extremely useful tool and has been successfully applied to solve various problems in a wide range of areas, including operations research, engineering, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as 1-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior PointMethods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider infeasible IPMs for the special case where the number of variables is much larger than the number of constraints. Using tools from Randomized Linear algebra, we present a preconditioning technique that, when combined with the Conjugate Gradient iterative solver, provably guarantees that infeasible IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real-world and synthetic data. Copyright © 2020, The Authors. All rights reserved.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

Computing Sparse GCD of Multivariate polynomials via Polynomial Interpolation

引用

Journal of Systems Science & Complexity 2018年第2期31卷 552-568页

作者： TANG Min LI Bingyu ZENG Zhenbing School of Mathematics and Computing Science Guangxi Key Laboratory of Cryptography and Information Security Guilin University of Electronic Technology Guilin 541004 China Shanghai Key Laboratory of Trustworthy Computing East China Normal University Shanghai 200062 China. Email: ***@***. School of Mathematics and Statistics Northeast Normal University Changchun 130024 China. Department of Mathematics Shanghai University Shanghai 200444 China

The problem of computing the greatest common divisor（GCD） of multivariate polynomials, as one of the most important tasks of computer algebra and symbolic computation in more general scope, has been studied extensively since the beginning of the interdisciplinary of mathematics with computer science. For many real applications such as digital image restoration and enhancement,robust control theory of nonlinear systems, L1-norm convex optimization in compressed sensing techniques, as well as algebraic decoding of Reed-Solomon and BCH codes, the concept of sparse GCD plays a core role where only the greatest common divisors with much fewer terms than the original polynomials are of interest due to the nature of problems or data structures. This paper presents two methods via multivariate polynomial interpolation which are based on the variation of Zippel＇s method and Ben-Or/Tiwari algorithm, respectively. To reduce computational complexity, probabilistic techniques and randomization are employed to deal with univariate GCD computation and univariate polynomial interpolation. The authors demonstrate the practical performance of our algorithms on a significant body of examples. The implemented experiment illustrates that our algorithms are efficient for a quite wide range of input.

关键词： Ben-Or/Tiwari algorithm multivariate polynomial interpolation sparse GCD Zippel＇s algorithm.

来源：评论

学校读者我要写书评

暂无评论

An Introduction to Compressed Sensing

引用

丛书名： Computational Science & Engineering

2019年

作者： M. Vidyasagar

ISBN: (数字)9781611976120

ISBN: (纸本)9781611976113

Compressed sensing is a relatively recent area of research that refers to the recovery of high-dimensional but low-complexity objects from a limited number of measurements. The topic has applications to signal/image processing and computer algorithms, and it draws from a variety of mathematical techniques such as graph theory, probability theory, linear algebra, and optimization. The author presents significant concepts never before discussed as well as new advances in the theory, providing an in-depth initiation to the field of compressed sensing.

An Introduction to Compressed Sensing

contains substantive material on graph theory and the design of binary measurement matrices, which is missing in recent texts despite being poised to play a key role in the future of compressed sensing theory;
covers several new developments in the field and is the only book to thoroughly study the problem of matrix recovery; and
supplies relevant results alongside their proofs in a compact and streamlined presentation that is easy to navigate.

The core audience for this book is engineers, computer scientists, and statisticians who are interested in compressed sensing. Professionals working in image processing, speech processing, or seismic signal processing will also find the book of interest.

关键词： Compressed sensing matrix completion graph theory optimization methods

来源：评论

学校读者我要写书评

暂无评论

Orbits of Abelian Automaton Groups 13th

Orbits of Abelian Automaton Groups

引用

13th International Conference on Language and Automata theory and applications, LATA 2019

作者： Becker, Tim Sutner, Klaus Department of Computer Sciences University of Wisconsin-Madison 1210 W. Dayton St. MadisonWI53706 United States Computer Science Department Carnegie Mellon University 5000 Forbes Avenue PittsburghPA15213 United States

ISBN: (纸本)9783030134341

Automaton groups are a class of self-similar groups generated by invertible finite-state transducers [11]. Extending the results of Nekrashevych and Sidki [12], we describe a useful embedding of abelian automaton groups into a corresponding algebraic number field, and give a polynomial time algorithm to compute this embedding. We apply this technique to study iteration of transductions in abelian automaton groups. Specifically, properties of this number field lead to a polynomial-time algorithm for deciding when the orbits of a transduction are a rational relation. These algorithms were implemented in the SageMath computer algebra system and are available online [2]. © 2019, Springer Nature Switzerland AG.

关键词： Embeddings

来源：评论

学校读者我要写书评

暂无评论

Fibonacci多项式的置换性质

引用

四川大学学报（自然科学版） 2020年第6期57卷 1047-1051页

作者：王智坚四川大学数学学院成都610064

置换多项式在代数学、组合学、数论、编码理论、密码学等领域中均有广泛而又重要的应用.本文主要研究Fibonacci多项式.通过计算其函数值的等幂和,本文得到了判定这些定义在有限域上的Fibonacci多项式为置换多项式的必要条件,解决了Ferna... 详细信息

置换多项式在代数学、组合学、数论、编码理论、密码学等领域中均有广泛而又重要的应用.本文主要研究Fibonacci多项式.通过计算其函数值的等幂和,本文得到了判定这些定义在有限域上的Fibonacci多项式为置换多项式的必要条件,解决了Fernando和Rashid提出的一个公开问题,从而推广了有关Fibonacci多项式置换性的已有结论.

关键词：置换性 Fibonacci多项式有限域编码理论

来源：评论

学校读者我要写书评

暂无评论

Robustness Analysis of Scaled Resource Allocation Models Using the Imperial PEPA Compiler

Robustness Analysis of Scaled Resource Allocation Models Usi...

引用

International Symposium on Parallel and Distributed Computing

作者： William S. Sanders Srishti Srivastava Ioana Banicescu Computer Science & Engineering Mississippi State University MS Mississippi State USA Computer Science University of Southern Indiana Evansville USA

ISBN: (数字)9781728189468

ISBN: (纸本)9781728189475

The increase in scale provided by distributed computing systems has expanded scientific discovery and engineering solutions. Stochastic modeling with Performance Evaluation Process algebra (PEPA) has been used to evaluate the robustness of static resource allocations in parallel and distributed computing systems. These evaluations have previously been performed through the PEPA Plug-In for the Eclipse Integrated Development Environment and have been limited by factors that include: i) the size and complexity of the underlying, in-use PEPA model, ii) a small number of resource allocation models available for analysis, and iii) the human interaction necessary to configure the PEPA Eclipse Plug-In, thus limiting potential automation. As the size and complexity of the underlying PEPA models increases, the number of states to be evaluated for each model also greatly increases, leading to a case of state space explosion. In this work, we validate the Imperial PEPA Compiler (IPC) as a replacement for the PEPA Eclipse Plug-In for the robustness analysis of resource allocations. We make available an implementation of the IPC as a Singularity container, as part of a larger online repository of PEPA resources. We then develop and test a programmatic method for generating PEPA models for resource allocations. When combined with our IPC container, this method allows automated analysis of resource allocation models at scale. The use of the IPC allows the evaluation of larger models than it is possible when using the PEPA Eclipse Plug-In. Moreover, the increases in scale in both model size and number of models, support the development of improved makespan targets for robustness metrics, including those among applications subject to perturbations at runtime, as found in typical parallel and distributed computing environments.

关键词： Computational modeling Robustness Resource management Analytical models Complexity theory Runtime algebra

来源：评论

学校读者我要写书评

暂无评论

polynomials, numerical triangles and sequences associated with the probability distribution of the hyperbolic cosine type for odd values of the parameter

引用

Journal of Physics: Conference Series 2021年第1期2052卷

作者： M S Tokmachev Yaroslav-the-Wise Novgorod State University Veliky Novgorod Russian Federation

The article introduces a new class of polynomials that first appeared in the probability distribution density function of the hyperbolic cosine type. With an integer change in one of the parameters of this distribution, polynomials in the form of a product of positive factors are written out with an increasing degree. Earlier, the author found a connection between the distribution of the hyperbolic cosine type and numerical sets, in particular, in the simplest cases with the triangle of coefficients of Bessel polynomials, the triangle of Stirling numbers, sequences of coefficients in the expansion of various functions, etc. Also from the distribution formed numerous numerical sequences, both new and widely known. Consideration of polynomials separately from the density function made it possible to reconstruct numerical sets of coefficients, ordered in the form of numerical triangles and numerical sequences. The connections between the elements of the sets are established. Among the sequences obtained, in the simplest cases, there are those known from others, for example, physical problems. However, the overwhelming majority of the found number sets have not been encountered earlier in the literature. The obvious applications of this research are number theory and algebra. And the interdisciplinarity of the results indicates the possibility of applications and enhances their practical significance in other areas of knowledge.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Quotients of orders in algebras obtained from skew polynomials with applications to coding theory

引用

COMMUNICATIONS IN algebra 2018年第11期46卷 5053-5072页

作者： Pumplun, Susanne Univ Nottingham Dept Math Sci Sch Math Sci Univ Pk Nottingham NG7 2RD England

We describe families of nonassociative finite unital rings that occur as quotients of natural nonassociative orders in generalized nonassociative cyclic division algebras over number fields. These natural orders have already been used to systematically construct fully diverse fast-decodable space-time block codes. We show how the quotients of natural orders can be employed for coset coding. Previous results by Oggier and Sethuraman involving quotients of orders in associative cyclic division algebras are obtained as special cases.

关键词： Coset code linear code nonassociative algebra skew polynomial ring space-time block code wiretap code

来源：评论

学校读者我要写书评

暂无评论

Gröbner basis over semigroup algebras: Algorithms and applications for sparse polynomial systems

arXiv

引用

arXiv 2019年

作者： Bender, Matías R. Faugère, Jean-Charles Tsigaridas, Elias Sorbonne Université Cnrs Inria Laboratoire D'Informatique de Paris 6 LIP6 Équipe PolSys ParisF-75005 France

Gröbner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, vision, biology, kinematics, cryptography, and optimization involve sparse systems where the input polynomials have a few non-zero terms. Our approach to exploit sparsity is to embed the systems in a semigroup algebra and to computeGrobner bases over this algebra. Up to now, the algorithms that follow this approach benefit from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. We introduce the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, we extend this algorithm to compute Grobner basis in the standard algebra and solve sparse polynomials systems over the torus (ℂ∗)n. The complexity of the algorithm depends on the Newton polytopes. Copyright © 2019, The Authors. All rights reserved.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Solving parametric systems of polynomial equations over the reals through hermite matrices

arXiv

引用

arXiv 2020年

作者： Le, Huu Phuoc El Din, Mohab Safey Sorbonne Université Cnrs Laboratoire d'Informatique de Paris 6 LIP6 Équipe Polsys Paris Cedex 05F-75252 France

We design a new algorithm for solving parametric systems of equations having finitely many complex solutions for generic values of the parameters. More precisely, let f = (f1, ⋯, fm) ⊂ [y][x] with y = (y1, ⋯, yt) and x = (x1, ⋯, xn), V ⊂ ℂt× ℂnbe the algebraic set defined by the simultaneous vanishing of the fi's and π be the projection (y, x) → y. Under the assumptions that f admits finitely many complex solutions when specializing y to generic values and that the ideal generated by f is radical, we solve the following algorithmic problem. On input f, we compute semi-algebraic formulas defining open semi-algebraic sets S1, ⋯, Sin the parameters' space tsuch that ∪ i=1Siis dense in tand, for 1 ≤ i ≤ , the number of real points in V ∩ π-1(η) is invariant when η ranges over Si. This algorithm exploits special properties of some well chosen monomial bases in the quotient algebra (y)[x]/I where I ⊂ (y)[x] is the ideal generated by f in (y)[x] as well as the specialization property of the so-called Hermite matrices which represent Hermite's quadratic forms. This allows us to obtain "compact" representations of the semi-algebraic sets Siby means of semialgebraic formulas encoding the signature of a given symmetric matrix. When f satisfies extra genericity assumptions (such as regularity), we use the theory of Gröbner bases to derive complexity bounds both on the number of arithmetic operations in and the degree of the output polynomials. More precisely, letting d be the maximal degrees of the fi's and D = n(d - 1)dn, we prove that, on a generic input f = (f1, ⋯, fn), one can compute those semialgebraic formulas using Õ((t+D/t)23tn2t+1d3nt+2(n+t)+1) arithmetic operations in and that the polynomials involved in these formulas have degree bounded by D. We report on practical experiments which illustrate the efficiency of this algorithm, both on generic parametric systems and parametric systems coming from applications since it allows us to solve systems which were out of rea

关键词： polynomials

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：