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

Efficient Grobner Basis Reductions for Formal Verification of Galois Field Arithmetic Circuits

IEEE TRANSACTIONS ON computer-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2013年第9期32卷 1409-1420页

作者： Lv, Jinpeng Kalla, Priyank Enescu, Florian Cadence Design Syst San Jose CA 95134 USA Univ Utah Dept Elect & Comp Engn Salt Lake City UT 84112 USA Georgia State Univ Dept Math & Stat Atlanta GA 30303 USA

Galois field arithmetic is a critical component in communication and security-related hardware, requiring dedicated arithmetic architectures for better performance. In many Galois field applications, such as cryptography, the data-path size in the circuits can be very large. Formal verification of such circuits is beyond the capabilities of contemporary verification techniques. This paper addresses formal verification of combinational arithmetic circuits over Galois fields of the type F-2k using a computer-algebra/algebraic-geometry-based approach. The verification problem is formulated as membership testing of a given specification polynomial in a corresponding ideal generated by the circuit constraints. Ideal membership testing requires the computation of a Grobner basis, which is computationally very expensive. To overcome this limitation, we analyze the circuit topology and derive a term order to represent the polynomials. Subsequently, using the theory of Grobner bases over F-2k, we show that this term order renders the set of polynomials itself a minimal Grobner basis of this ideal. Consequently, the verification test reduces to a much simpler case of Grobner basis reduction via polynomial division, significantly enhancing verification efficiency. To further improve our approach, we exploit the concepts presented in the F4 algorithm for Grobner basis, and show that the verification test can be formulated as Gaussian elimination on a matrix representation of the problem. Finally, we demonstrate the ability of our approach to verify the correctness of, and detect bugs in, up to 163-bit circuits in F-2163-whereas verification utilizing contemporary techniques proves infeasible.

关键词： Arithmetic circuits computer algebra formal verification Galois fields Grobner bases

来源：评论

学校读者我要写书评

暂无评论

Numerical Quadratures Using the Interpolation Method of Hurwitz-Radon Matrices

引用

Advances in Linear algebra & Matrix theory 2014年第2期4卷 100-108页

作者： Dariusz Jacek Jakóbczak Department of Computer Science and Management

Mathematics and computer sciences need suitable methods for numerical calculations of integrals. Classical methods, based on polynomial interpolation, have many weak sides: they are useless to interpolate the function that fails to be differentiable at one point or differs from the shape of polynomials considerably. We cannot forget about the Runge’s phenomenon. To deal with numerical interpolation and integration dedicated methods should be constructed. One of them, called by author the method of Hurwitz-Radon Matrices (MHR), can be used in reconstruction and interpolation of curves in the plane. This novel method is based on a family of Hurwitz-Radon (HR) matrices. The matrices are skew-symmetric and possess columns composed of orthogonal vectors. The operator of Hurwitz-Radon (OHR), built from that matrices, is described. It is shown how to create the orthogonal and discrete OHR and how to use it in a process of function interpolation and numerical integration. Created from the family of N-1 HR matrices and completed with the identical matrix, system of matrices is orthogonal only for vector spaces of dimensions N = 2, 4 or 8. Orthogonality of columns and rows is very significant for stability and high precision of calculations. MHR method is interpolating the curve point by point without using any formula of function. Main features of MHR method are: accuracy of curve reconstruction depending on number of nodes and method of choosing nodes;interpolation of L points of the curve is connected with the computational cost of rank O(L);MHR interpolation is not a linear interpolation.

关键词： Curve Interpolation Numerical Integration Hurwitz-Radon Matrices MHR Method

来源：评论

学校读者我要写书评

暂无评论

Stability and Spectral Properties in the Max algebra with applications in Ranking Schemes

Stability and Spectral Properties in the Max Algebra with Ap...

引用

作者： Buket Benek Gursoy National University of Ireland

学位级别：博士

This thesis is concerned with the correspondence between the max algebra and non-negative linear algebra. It is motivated by the Perron-Frobenius theory as a powerful tool in ranking applications. Throughout the thesis, we consider max-algebraic versions of some standard results of non-negative linear algeb- ra. We are specifically interested in the spectral and stability properties of non-negative matrices. We see that many well-known theorems in this context extend to the max algebra. We also consider how we can relate these results to ranking applications in decision making problems. In particular, we focus on deriving ranking schemes for the Analytic Hierarchy Process (AHP). We start by describing fundamental concepts that will be used throughout the thesis after a general introduction. We also state well-known results in both non-negative linear algebra and the max algebra. We are next interested in the characterisation of the spectral properties of mat- rix polynomials. We analyse their relation to multi-step difference equations. We show how results for matrix polynomials in the conventional algebra carry over naturally to the max-algebraic setting. We also consider an extension of the so-called Fundamental Theorem of Demography to the max algebra. Using the concept of a multigraph, we prove that a number of inequalities related to the spectral radius of a matrix polynomial are also true for its largest max eigenvalue. We are next concerned with the asymptotic stability of non-negative matrices in the context of dynamical systems. We are motivated by the relation of P -matrices and positive stability of non-negative matrices. We discuss how equivalent conditions connected with this relation echo similar results over the max algebra. Moreover, we consider extensions of the properties of sets of P -matrices to the max algebra. In this direction, we highlight the central role of the max version of the generalised spectral radius. We then focus on ranking applica

关键词：

来源：评论

学校读者我要写书评

暂无评论

Compositions and collisions at degree p²

引用

JOURNAL OF SYMBOLIC COMPUTATION 2013年第Dec.期59卷 113-145页

作者： Blankertz, Raoul von zur Gathen, Joachim Ziegler, Konstantin Univ Bonn B IT D-53113 Bonn Germany

A univariate polynomial f over a field is decomposable if f = g circle h = g(h) for nonlinear polynomials g and h. In order to count the decomposables, one wants to know, under a suitable normalization, the number of equal-degree collisions of the form f = g circle h = g* circle h* with (g, h) not equal (g*, h*) and deg g = deg g*. Such collisions only occur in the wild case, where the field characteristic p divides deg f. Reasonable bounds on the number of decomposables over a finite field are known, but they are less sharp in the wild case, in particular for degree p(2). We provide a classification of all polynomials of degree p(2) with a collision. It yields the exact number of decomposable polynomials of degree p(2) over a finite field of characteristic p. We also present an efficient algorithm that determines whether a given polynomial of degree p(2) has a collision or not. (C) 2013 Elsevier B.V. All rights reserved.

关键词： computer algebra Finite fields Wild polynomial decomposition Equal-degree collisions Ramification theory of function fields Counting special polynomials

来源：评论

学校读者我要写书评

暂无评论

Computational number theory /

引用

1000年

作者： Das Abhijit

来源：内蒙古大学图书馆图书评论

学校读者我要写书评

暂无评论

Analysis approach to finite monoids

引用

FIXED POINT theory AND applications 2013年第1期2013卷 1-18页

作者： Cevik, A. Sinan Cangul, I. Naci Simsek, Yilmaz Selcuk Univ Dept Math Fac Sci TR-42075 Konya Turkey Uludag Univ Dept Math Fac Arts & Sci TR-16059 Bursa Turkey Akdeniz Univ Dept Math Fac Art & Sci TR-07058 Antalya Turkey

In a previous paper by the authors, a new approach between algebra and analysis has been recently developed. In detail, it has been generally described how one can express some algebraic properties in terms of special generating functions. To continue the study of this approach, in here, we state and prove that the presentation which has the minimal number of generators of the split extension of two finite monogenic monoids has different sets of generating functions (such that the number of these functions is equal to the number of generators) that represent the exponent sums of the generating pictures of this presentation. This study can be thought of as a mixture of pure analysis, topology and geometry within the purposes of this journal. AMS Subject Classification: 11B68, 11S40, 12D10, 20M05, 20M50, 26C05, 26C10.

关键词： efficiency p-Cockcroft property split extension generating functions Stirling numbers array polynomials

来源：评论

学校读者我要写书评

暂无评论

Concise computer Mathematics: Tutorials on theory and Problems 1

引用

丛书名： SpringerBriefs in computer Science

2013年

作者： Ovidiu Bagdasar (auth.)

ISBN: (数字)9783319017518

ISBN: (纸本)9783319017501;9783319017518

Adapted from a modular undergraduate course on computational mathematics, Concise computer Mathematics delivers an easily accessible, self-contained introduction to the basic notions of mathematics necessary for a computer science degree. The text reflects the need to quickly introduce students from a variety of educational backgrounds to a number of essential mathematical concepts. The material is divided into four units: discrete mathematics (sets, relations, functions), logic (Boolean types, truth tables, proofs), linear algebra (vectors, matrices and graphics), and special topics (graph theory, number theory, basic elements of calculus). The chapters contain a brief theoretical presentation of the topic, followed by a selection of problems (which are direct applications of the theory) and additional supplementary problems (which may require a bit more work). Each chapter ends with answers or worked solutions for all of the problems.

关键词：

来源：评论

学校读者我要写书评

暂无评论

The Complexity of University Curricula According to Course Cruciality

The Complexity of University Curricula According to Course C...

引用

International Conference on Complex, Intelligent and Software Intensive Systems, CISIS

作者： Ahmad Slim Jarred Kozlick Gregory L. Heileman Chaouki T. Abdallah Department of Electrical and Computer Engineering University of New Mexico Albuquerque NM USA

Many universities have recently focused significant efforts on enhancing their graduation rates. Numerous factors may impact a student's ability to succeed and ultimately graduate, including pre-university preparation, as well as the student support services provided by a university. However, even the best efforts to improve in these areas may fail if other institutional factors overwhelm their ability to facilitate student progress. Specifically, in this paper we consider degree to which the underlying curriculum that a student must traverse in order to earn a degree impacts progress. Using complex network analysis and graph theory, this paper proposes a framework for analyzing university course networks at the university, college and departmental levels. The analyses we provide are based on quantifying the importance of a course based on its delay and blocking factors, as well as the number of curricula that incorporate the course, leading to a metric we refer to as the course cruciality. Experimental results, using data from the University of New Mexico, show that the distribution of course cruciality follows a power law distribution. applications of the proposed framework are extended to study the complexity of curricula within colleges as well as the tendency of a university's disciplines to associate with others that are unlike them. This work may be useful to both students and decision makers at universities as it presents a robust framework for analyzing the ease of flow of students through curricula, which may lead to improvements that facilitate improved student success.

关键词： Educational institutions Complexity theory Delays algebra computers

来源：评论

学校读者我要写书评

暂无评论

Minimal and random generation of permutation and matrix groups

引用

JOURNAL OF algebra 2013年 387卷 195-214页

作者： Holt, Derek F. Roney-Dougal, Colva M. Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ St Andrews Math Inst St Andrews KY16 9SS Fife Scotland

We prove explicit bounds on the numbers of elements needed to generate various types of finite permutation groups and finite completely reducible matrix groups, and present examples to show that they are sharp in all cases. The bounds are linear in the degree of the permutation or matrix group in general, and logarithmic when the group is primitive. They can be combined with results of Lubotzky to produce explicit bounds on the number of random elements required to generate these groups with a specified probability. These results have important applications to computational group theory. Our proofs are inductive and largely theoretical, but we use computer calculations to establish the bounds in a number of specific small cases. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Finite groups Generation of groups Matrix groups Permutation groups probabilistic and asymptotic group theory

来源：评论

学校读者我要写书评

暂无评论

Computing Tutte polynomials of Contact Networks in Classrooms

Computing Tutte Polynomials of Contact Networks in Classroom...

引用

Conference on Sensing Technologies for Global Health, Military Medicine, and Environmental Monitoring III

作者： Hincapie, Doracelly Ospina, Juan Univ Antioquia Natl Sch Publ Hlth Epidemiol Grp Medellin Colombia

ISBN: (纸本)9780819495143

Objective: The topological complexity of contact networks in classrooms and the potential transmission of an infectious disease were analyzed by sex and age. Methods: The Tutte polynomials, some topological properties and the number of spanning trees were used to algebraically compute the topological complexity. Computations were made with the Maple package Graphtheory. Published data of mutually reported social contacts within a classroom taken from primary school, consisting of children in the age ranges of 4-5, 7-8 and 10-11, were used. Results: The algebraic complexity of the Tutte polynomial and the probability of disease transmission increases with age. The contact networks are not bipartite graphs, gender segregation was observed especially in younger children. Conclusion: Tutte polynomials are tools to understand the topology of the contact networks and to derive numerical indexes of such topologies. It is possible to establish relationships between the Tutte polynomial of a given contact network and the potential transmission of an infectious disease within such network

关键词： Graph theory Tutte polynomials computer algebra Software Contact networks analysis Computational Epidemiology

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：