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

arXiv 2024年

作者： Belgacem, Ismail Edwards, Roderick Farcot, Etienne University of Victoria Canada School of Mathematical Sciences University of Nottingham United Kingdom

Glass networks model systems of variables that interact via sharp switching. A body of theory has been developed over several decades that, in principle, allows rigorous proof of dynamical properties in high dimensions that is not normally feasible in nonlinear dynamical systems. Previous work has, however, used examples of dimension no higher than 6 to illustrate the methods. Here we show that the same tools can be applied in dimensions at least as high as 20. An important application of Glass networks is to a recently-proposed design of a True Random number Generator that is based on an intrinsically chaotic electronic circuit. In order for analysis to be meaningful for the application, the dimension must be at least 20. Bifurcation diagrams show what appear to be periodic and chaotic bands. Here we demonstrate that the analytic tools for Glass networks can be used to rigorously show where periodic orbits are lost, and the types of bifurcations that occur there. The main tools are linear algebra and the stability theory of Poincaré maps. All main steps can be automated, and we provide computer code. The methods reviewed here have the potential for many other applications involving sharply switching interactions, such as artificial neural networks. © 2024, CC BY-NC-SA.

关键词： Random number generation

来源：评论

学校读者我要写书评

暂无评论

On the product of the singular values of a binary tensor

引用

ISRAEL JOURNAL OF MATHEMATICS 2021年第1期243卷 233-272页

作者： Sodomaco, Luca Aalto Univ Dept Math & Syst Anal FI-00076 Espoo Finland

A real binary tensor consists of 2(d) real entries arranged into hypercube format 2(xd). For d = 2, a real binary tensor is a 2 x 2 matrix with two singular values. Their product is the determinant. We generalize this formula to d >= 2. Given a partition mu(sic)d and a mu-symmetric real binary tensor t, we study the distance function from t to the variety XR mu of mu-symmetric real binary tensors of rank one. The study of the local minima of this function is related to the computation of the singular values of t. Denoting with X mu the complexification of X-mu(R), the Euclidean Distance polynomial EDpoly X. mu,t ("2) of the dual variety of X-mu at t has among its roots the singular values of t. On one hand, the lowest coefficient of EDpoly X-mu(v) t(epsilon(2)) is the square of the mu-discriminant of t times a product of sum of squares polynomials. On the other hand, we describe the variety of mu-symmetric binary tensors that do not admit the maximum number of singular values, counted with multiplicity. Finally, we compute symbolically all the coefficients of EDpoly X. mu,t("2) for tensors of format 2 x 2 x 2.

关键词： Mathematics general algebra Group theory and Generalizations Analysis applications of Mathematics Theoretical Mathematical and Computational Physics

来源：评论

学校读者我要写书评

暂无评论

Fast, algebraic Multivariate Multipoint Evaluation in Small Characteristic and applications 2022

Fast, Algebraic Multivariate Multipoint Evaluation in Small ...

引用

54th Annual ACM SIGACT Symposium on theory of Computing (STOC)

作者： Bhargava, Vishwas Ghosh, Sumanta Kumar, Mrinal Mohapatra, Chandra Kanta Rutgers State Univ Comp Sci Piscataway NJ 08854 USA CALTECH Comp & Math Sci Pasadena CA 91125 USA Indian Inst Technol Comp Sci & Engn Mumbai Maharashtra India

ISBN: (纸本)9781450392648

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans and Kedlaya & Umans gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables n is at most d(o(1)) where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case (i.e. n is not an element of d(o(1))) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field Fq of characteristic p which evaluates an n-variate polynomial of degree less than d in each variable on N inputs in time ((N + d(n))(1+ o(1)) poly(logq, d, n, p)) provided that p is at most d(o(1)), and q is at most (exp( . . . (exp(d)))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g. n is not an element of d(o(1))), this is the first nearly linear time algorithm for this problem over any ( large enough) field.

关键词： Multipoint evaluation Matrix rigidity Modular composition Polynomial evaluation Data structures algebraic circuits Vandermonde matrix

来源：评论

学校读者我要写书评

暂无评论

The Principle of Mathematical Induction: applications in Physical Optics

引用

JOURNAL OF APPLIED MATHEMATICS 2022年第0期2022卷

作者： Thomas, Joseph Ivin Natl Inst Adv Studies Sch Nat Sci & Engn IISc Campus Bangalore India

The bare rudiments of the principle of mathematical induction as a method of proof date back to ancient times. In the contemporary university milieu, the demonstrative scheme is taught as part of a course in discrete mathematics, set theory, number theory, graph theory, group theory, game theory, linear algebra, logic, and combinatorics. In theoretical computer science, it bears the pivotal role of developing the appropriate cognitive skills necessary for the effective design and implementation of algorithms, assessing for both their correctness and complexity. Pure mathematics and computer science aside, the scope of its utility in the physical sciences remains limited. Following an outline of some elementary concepts from vector algebra and phasor analysis, the proofs by induction of a couple of salient results in multiple-slit interferometry are presented, viz., the fringe intensity distribution formula and the upper bound of the total fringe count. These specific optical instantiations serve to illustrate the versatility and power of the principle at tackling real-world problems. It thereby makes a welcome departure from the popular view of induction as a mere last resort for proving abstract mathematical statements.

关键词： Group theory

来源：评论

学校读者我要写书评

暂无评论

SparseAuto: An Auto-Scheduler for Sparse Tensor Computations Using Recursive Loop Nest Restructuring

arXiv

引用

arXiv 2023年

作者： Dias, Adhitha Anderson, Logan Sundararajah, Kirshanthan Pelenitsyn, Artem Kulkarni, Milind Electrical and Computer Engineering Purdue University 610 Purdue Mall West LafayetteIN47906 United States Computer Science Virginia Tech BlacksburgVA24061 United States

Automated code generation and performance enhancements for sparse tensor algebra have become essential in many real-world applications, such as quantum computing, physical simulations, computational chemistry, and machine learning. General sparse tensor algebra compilers are not always versatile enough to generate asymptotically optimal code for sparse tensor contractions. This paper shows how to generate asymptotically better schedules for complex sparse tensor expressions using kernel fission and fusion. We present generalized loop restructuring transformations to reduce asymptotic time complexity and memory footprint. Furthermore, we present an auto-scheduler that uses a partially ordered set (poset)-based cost model that uses both time and auxiliary memory complexities to prune the search space of schedules. In addition, we highlight the use of Satisfiability Module theory (SMT) solvers in sparse auto-schedulers to approximate the Pareto frontier of better schedules to the smallest number of possible schedules, with user-defined constraints available at compile-time. Finally, we show that our auto-scheduler can select better-performing schedules and generate code for them. Our results show that the auto-scheduler provided schedules achieve orders-of-magnitude speedup compared to the code generated by the Tensor algebra Compiler (TACO) for several computations on different real-world tensors. © 2023, CC BY.

关键词： Tensors

来源：评论

学校读者我要写书评

暂无评论

STRUCTURED INVERSION OF THE BERNSTEIN MASS MATRIX

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND applications 2020年第2期41卷 413-431页

作者： Allen, Larry Kirby, Robert C. Baylor Univ Dept Math One Bear Pl 97328 Waco TX 76798 USA

Bernstein polynomials, long a staple of approximation theory and computational geometry, have also increasingly become of interest in finite element methods. Many fundamental problems in interpolation and approximation give rise to interesting linear algebra questions. In [13], we gave block-structured algorithms for inverting the Bernstein mass matrix on simplicial cells but did not study fast algorithms for the univariate case. Here, we give several approaches to inverting the univariate mass matrix based on exact formulae for the inverse;decompositions of the inverse in terms of Hankel, Toeplitz, and diagonal matrices;and a spectral decomposition. In particular, the eigen-decomposition can be explicitly constructed in O(n(2)) operations, while its accuracy for solving linear systems is comparable to that of the Cholesky decomposition. Moreover, we study conditioning and accuracy of these methods from the standpoint of the effect of roundoff error in the L-2 norm on polynomials, showing that the conditioning in this case is far less extreme than in the standard 2-norm.

关键词： Bernstein polynomials Legendre polynomials Bernstein mass matrix matrix inverse Bezout matrix spectral decomposition fast algorithm conditioning

来源：评论

学校读者我要写书评

暂无评论

Short definitions in constraint languages

arXiv

引用

arXiv 2023年

作者： Bulín, Jakub Kompatscher, Michael Department of Theoretical Computer Science and Mathematical Logic Faculty of Mathematics and Physics Charles University Prague Czech Republic Department of Algebra Faculty of Mathematics and Physics Charles University Prague Czech Republic

A first-order formula is called primitive positive (pp) if it only admits the use of existential quantifiers and conjunction. Pp-formulas are a central concept in (fixed-template) constraint satisfaction since CSP(Γ) can be viewed as the problem of deciding the primitive positive theory of Γ, and pp-definability captures gadget reductions between CSPs. An important class of tractable constraint languages Γ is characterized by having few subpowers, that is, the number of n-ary relations pp-definable from Γ is bounded by 2p(n) for some polynomial p(n). In this paper we study a restriction of this property, stating that every pp-definable relation is definable by a pp-formula of polynomial length. We conjecture that the existence of such short definitions is actually equivalent to Γ having few subpowers, and verify this conjecture for a large subclass that, in particular, includes all constraint languages on three-element domains. We furthermore discuss how our conjecture imposes an upper complexity bound of co-NP on the subpower membership problem of algebras with few *** Codes 08A70 © 2023, CC BY.

关键词： polynomials

来源：评论

学校读者我要写书评

暂无评论

Root polynomials and their role in the theory of matrix polynomials

引用

LINEAR algebra AND ITS applications 2020年 584卷 37-78页

作者： Dopico, Froilan M. Noferini, Vanni Univ Carlos III Madrid Dept Matemat Avda Univ 30 Leganes 28911 Spain Aalto Univ Dept Math & Syst Anal POB 11100 FI-00076 Aalto Finland

We develop a complete and rigorous theory of root polynomials of arbitrary matrix polynomials, i.e., either regular or singular, and study how these vector polynomials are related to the spectral properties of matrix polynomials. We pay particular attention to the so-called maximal sets of root polynomials and prove that they carry complete information about the eigenvalues (finite or infinite) of matrix polynomials and that they are related to the matrices that transform any matrix polynomial into its Smith form. In addition, we describe clearly, for the first time in the literature, the extremality properties of such maximal sets and identify some of them whose vectors have minimal grade. Once the main theoretical properties of root polynomials have been established, the interaction of root polynomials with three problems that have attracted considerable attention in the literature is analyzed. More precisely, we study the change of root polynomials under rational transformations, or reparametrizations, of matrix polynomials, the recovery of the root polynomials of a matrix polynomial from those of its most important linearizations, and the relationship between the root polynomials of two dual pencils. We emphasize that for the case of regular matrix polynomials all the results in this paper can be translated into the language of Jordan chains, as a consequence of the well known relationship between root polynomials and Jordan chains. Therefore, a number of open problems are also solved for Jordan chains of regular matrix polynomials. We also briefly discuss how root polynomials can be used to define eigenvectors and eigenspaces for singular matrix polynomials. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Matrix polynomials Polynomial matrices Root polynomials mu-independent set Complete set Maximal set Minimaximal set Eigenvalues Minimal bases Singular Eigenvectors of singular matrix polynomials Jordan chains

来源：评论

学校读者我要写书评

暂无评论

A Survey on Time Series Data Classification: Blockchain Technologies and Security Concerns

引用

Procedia computer Science 2024年 246卷 961-970页

作者： Ahmed Faris Alsayyad Alaa Abid Muslam Abid Ali Mohamed Mabrouk Ahmed Al-Shammari Mounir Zrigui Research Laboratory in Algebra Numbers Theory and Intelligent Systems RLANTIS University of Monastir Monastir Tunisia Al-Qadisiyah University Al-Qadisiyah Iraq Military Academy Fondok Jedid Tunisia Department of Computer Science College of Computer Science and Information Technology University of Al-Qadisiyah Al Diwaniyah 58002 Iraq

The difficulties about user security and privacy have appeared as significant concerns in recent years. The number of cyber-attacks grows at a concerning velocity, hence rendering internet users susceptible to malicious activities perpetrated by hackers. Data mining approaches are employed to extract accurate results from massive and complex databases. Furthermore, the utilization of Blockchain (BC) approaches is increasingly popular in current Internet of Things (IoT) applications as an opportunity to address issues related to privacy and security. Lots of studies have been performed on algorithms for data mining and techniques concerning blockchain. Time series data is a commonly used form of data. Time Series Classification (TSC) refers to the creation of predictive models that generate a target variable or label based on linear or sequential data inputs across a considerable duration. The possible results may be presented in either ordinal or numerical form. Even so, previous studies have shown major limitations when it comes to handling privacy and security issues that can’t be applicable in dynamic instances, as well as the substantial computational cost necessary. Moreover, correctly determining the amount of sensitive parameters required to complete the classification process remains a challenge. We have put forth a comprehensive survey on the classification of blockchain data. In the first phase of our study, we conducted an analysis and categorization of both conventional data classification approaches and contemporary time series data classification techniques. We further discussed limitations and strengths of existing techniques. Finally, we highlight future research problems and directions.

关键词： Blockchain Data Mining Time Series Classification Data Classification Security

来源：评论

学校读者我要写书评

暂无评论

Finite fields, with applications to combinatorics /

引用

丛书名： Student mathematical library

2022年

作者： Soundararajan Kannan

ISBN: (纸本)9781470469306

This book uses finite field theory as a hook to introduce the reader to a range of ideas from algebra and number theory. It constructs all finite fields from scratch and shows that they are unique up to isomorphism. As a payoff, several combinatorial applications of finite fields are given: Sidon sets and perfect difference sets, de Bruijn sequences and a magic trick of Persi Diaconis, and the polynomial time algorithm for primality testing due to Agrawal, Kayal and Saxena. The book forms the basis for a one term intensive course with students meeting weekly for multiple lectures and a discussion session. Readers can expect to develop familiarity with ideas in algebra (groups, rings and fields), and elementary number theory, which would help with later classes where these are developed in greater detail. And they will enjoy seeing the AKS primality test application tying together the many disparate topics from the book. The pre-requisites for reading this book are minimal: familiarity with proof writing, some linear algebra, and one variable calculus is assumed. This book is aimed at incoming undergraduate students with a strong interest in mathematics or computer science.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：