Algorithms and Computation in Mathematics – serie

This book is divided into two parts, one theoretical and one focusing on applications, and offers a complete description of the Canonical Gröbner Cover, the most accurate algebraic method for discussing parametric polynomial systems.

This edited volume presents a fascinating collection of lecture notes focusing on differential equations from two viewpoints: formal calculus (through the theory of Gröbner bases) and geometry (via quiver theory).

This edited volume presents a fascinating collection of lecture notes focusing on differential equations from two viewpoints: formal calculus (through the theory of Gröbner bases) and geometry (via quiver theory).

This monograph provides a self-contained presentation of the foundations of finite fields, including a detailed treatment of their algebraic closures. It also covers important advanced topics which are not yet found in textbooks: the primitive normal basis theorem, the existence of primitive elements in affine hyperplanes, and the Niederreiter method for factoring polynomials over finite fields.We give streamlined and/or clearer proofs for many fundamental results and treat some classical material in an innovative manner. In particular, we emphasize the interplay between arithmetical and structural results, and we introduce Berlekamp algebras in a novel way which provides a deeper understanding of Berlekamp's celebrated factorization algorithm.The book provides a thorough grounding in finite field theory for graduate students and researchers in mathematics. In view of its emphasis on applicable and computational aspects, it is also useful for readers working in information and communication engineering, for instance, in signal processing, coding theory, cryptography or computer science.

Defined as solutions of linear differential or difference equations with polynomial coefficients, D-finite functions play an important role in various areas of mathematics. This book is a comprehensive introduction to the theory of these functions with a special emphasis on computer algebra algorithms for computing with them: algorithms for detecting relations from given data, for evaluating D-finite functions, for executing closure properties, for obtaining various kinds of “explicit” expressions, for factoring operators, and for definite and indefinite symbolic summation and integration are explained in detail.The book comes “with batteries included” in the sense that it requires no background in computer algebra as the relevant facts from this area are summarized in the beginning. This makes the book accessible to a wide range of readers, from mathematics students who plan to work themselves on D-finite functions to researchers who want to apply the theory to their own work. Hundreds of exercises invite the reader to apply the techniques in the book and explore further aspects of the theory on their own. Solutions to all exercises are given in the appendix.When algorithms for D-finite functions came up in the early 1990s, computer proofs were met with a certain skepticism. Fortunately, these times are over and computer algebra has become a standard tool for many mathematicians. Yet, this powerful machinery is still not as widely known as it deserves. This book helps to spread the word that certain tasks can be safely delegated to a computer algebra system, and also what the limitations of these techniques are.

Defined as solutions of linear differential or difference equations with polynomial coefficients, D-finite functions play an important role in various areas of mathematics. This book is a comprehensive introduction to the theory of these functions with a special emphasis on computer algebra algorithms for computing with them: algorithms for detecting relations from given data, for evaluating D-finite functions, for executing closure properties, for obtaining various kinds of “explicit” expressions, for factoring operators, and for definite and indefinite symbolic summation and integration are explained in detail.The book comes “with batteries included” in the sense that it requires no background in computer algebra as the relevant facts from this area are summarized in the beginning. This makes the book accessible to a wide range of readers, from mathematics students who plan to work themselves on D-finite functions to researchers who want to apply the theory to their own work. Hundreds of exercises invite the reader to apply the techniques in the book and explore further aspects of the theory on their own. Solutions to all exercises are given in the appendix.When algorithms for D-finite functions came up in the early 1990s, computer proofs were met with a certain skepticism. Fortunately, these times are over and computer algebra has become a standard tool for many mathematicians. Yet, this powerful machinery is still not as widely known as it deserves. This book helps to spread the word that certain tasks can be safely delegated to a computer algebra system, and also what the limitations of these techniques are.

Beginning with its origins in the pioneering work of W.T. Tutte in 1947, this monograph systematically traces through some of the impressive developments in matching theory. A graph is matchable if it has a perfect matching. A matching covered graph is a connected graph on at least two vertices in which each edge is covered by some perfect matching. The theory of matching covered graphs, though of relatively recent vintage, has an array of interesting results with elegant proofs, several surprising applications and challenging unsolved problems. The aim of this book is to present the material in a well-organized manner with plenty of examples and illustrations so as to make it accessible to undergraduates, and also to unify the existing theory and point out new avenues to explore so as to make it attractive to graduate students.

Beginning with its origins in the pioneering work of W.T. Tutte in 1947, this monograph systematically traces through some of the impressive developments in matching theory. A graph is matchable if it has a perfect matching. A matching covered graph is a connected graph on at least two vertices in which each edge is covered by some perfect matching. The theory of matching covered graphs, though of relatively recent vintage, has an array of interesting results with elegant proofs, several surprising applications and challenging unsolved problems. The aim of this book is to present the material in a well-organized manner with plenty of examples and illustrations so as to make it accessible to undergraduates, and also to unify the existing theory and point out new avenues to explore so as to make it attractive to graduate students.

This book presents version 1.0 of the new Computer Algebra System OSCAR.Written in Julia, OSCAR builds on and vastly extends four cornerstone systems:ANTIC for number theory, GAP for group and representation theory,  polymake for polyhedral and tropical geometry, and  Singular for commutative algebra and algebraic geometry.It offers powerful computational tools that transcend the boundaries of the individual disciplines involved.It is freely available, open source software. The book is an invitation to use OSCAR.  With discussions of theoretical and algorithmic aspects included, it offers a multitude of explicit code snippets.  These are valuable for interested researchers from graduate students through established experts.

Moving forward, the third part of the book explores numerical algorithms for solving filtering problems, including the Yau-Yau algorithm, direct methods, classical filtering algorithms like the particle filter, and the intersection of filtering theory with deep learning.

This text presents a comprehensive and unified treatment of nonlinear filtering theory, with a strong emphasis on its mathematical underpinnings. It is tailored to meet the needs of a diverse readership, including mathematically inclined engineers and scientists at both graduate and post-graduate levels. What sets this book apart from other treatments of the topic is twofold. Firstly, it offers a complete treatment of filtering theory, providing readers with a thorough understanding of the subject. Secondly, it introduces updated methodologies and applications that are crucial in today’s landscape. These include finite-dimensional filters, the Yau-Yau algorithm, direct methods, and the integration of deep learning with filtering problems. The book will be an invaluable resource for researchers and practitioners for years to come.With a rich historical backdrop dating back to Gauss and Wiener, the exposition delves into the fundamental principles underpinning the estimation of stochastic processes amidst noisy observations—a critical tool in various applied domains such as aircraft navigation, solar mapping, and orbit determination, to name just a few. Substantive exercises and examples given in each chapter provide the reader with opportunities to appreciate applications and ample ways to test their understanding of the topics covered. An especially nice feature for those studying the subject independent of a traditional course setting is the inclusion of solutions to exercises at the end of the book.The book is structured into three cohesive parts, each designed to build the reader's understanding of nonlinear filtering theory.  In the first part, foundational concepts from probability theory, stochastic processes, stochastic differential equations, and optimization are introduced, providing readers with the necessary mathematical background. The second part delves into theoretical aspects of filtering theory, covering topics such as the stochastic partial differential equation governing the posterior density function of the state, and the estimation algebra theory of systems with finite-dimensional filters. Moving forward, the third part of the book explores numerical algorithms for solving filtering problems, including the Yau-Yau algorithm, direct methods, classical filtering algorithms like the particle filter, and the intersection of filtering theory with deep learning.

Symbolic asymptotics has recently undergone considerable theoretical development, especially in areas where power series are no longer an appropriate tool. Implementation is beginning to follow.The present book, written by one of the leading specialists in the area, is currently the only one to treat this part of symbolic asymptotics. It contains a good deal of interesting material in a new, developing field of mathematics at the intersection of algebra, analysis and computing, presented in a lively and readable way. The associated areas of zero equivalence and Hardy fields are also covered.The book is intended to be accessible to anyone with a good general background in mathematics, but it nonetheless gets right to the cutting edge of active research. Some results appear here for the first time, while others have hitherto only been given in preprints. Due to its clear presentation, this book is interesting for a broad audience of mathematicians and theoretical computer scientists.

From the reviews: "... Many parts of the book can be read by anyone with a basic abstract algebra course... it was one of the author's intentions to equip students who are interested in computational problems with the necessary algebraic background in pure mathematics and to encourage them to do further research in commutative algebra and algebraic geometry. But researchers will also benefit from this exposition. They will find an up-to-date description of the related research ... The reviewer recommends the book to anybody who is interested in commutative algebra and algebraic geometry and its computational aspects." Math. Reviews 2002"... a sophisticated notebook, with plenty of suggestions, examples and cross references ... It is a welcome new and deep exploration into commutative algebra and its relations with algebraic geometry. It is full of results, from simple tricks to more elaborate constructions, all having in common a computational and constructive nature..." Jahresberichte der DMV 1999

Symbolic Integration I is destined to become the standard reference work in the field. Manuel Bronstein is a leading expert on this topic and his book is the first to treat the subject both comprehensively and in sufficient detail - incorporating new results along the way. The book addresses mathematicians and computer scientists interested in symbolic computation, developers and programmers of computer algebra systems as well as users of symbolic integration methods. Many algorithms are given in pseudocode ready for immediate implementation, making the book equally suitable as a textbook for lecture courses on symbolic integration.This second edition offers a new chapter on parallel integration, a number of other improvements and a couple of additional exercises. From the reviews of the first edition: "...The writing is excellent, and the author provides a clear and coherent treatment of the problem of symbolic integration of transcendental functions." F. Winkler, Computing Reviews 1997

Ergodic theory is hard to study because it is based on measure theory, which is a technically difficult subject to master for ordinary students, especially for physics majors. One last remark: The last chapter explains the relation between entropy and data compression, which belongs to information theory and not to ergodic theory.

This book provides a general introduction to modern mathematical aspects in computing with multivariate polynomials and in solving algebraic systems. It presents the state of the art in several symbolic, numeric, and symbolic-numeric techniques, including effective and algorithmic methods in algebraic geometry and computational algebra, complexity issues, and applications ranging from statistics and geometric modelling to robotics and vision.Graduate students, as well as researchers in related areas, will find an excellent introduction to currently interesting topics. These cover Groebner and border bases, multivariate resultants, residues, primary decomposition, multivariate polynomial factorization, homotopy continuation, complexity issues, and their applications.

The fascinating theory of error-correcting codes is a rather new addition to the list of mathematical disciplines. It grew out of the need to communicate information electronically, and is currently no more than 60 years old. - ing an applied discipline by de?nition, a surprisingly large number of pure mathematical areas tie into Coding Theory. If one were to name just the most important connections, one would start of course with Linear Algebra, then list Algebra and Combinatorics, and further mention Number Theory and - ometry as well as Algebraic Geometry. Being a thorough introduction to the ?eld, this book starts from the very beginning, which is the channel model of communication in the presence of noise. From there, we develop the fundamental concepts of error-correcting codes, like the Hamming metric and the maximum likelihood decoding pr- ciple. After discussing dual codes and simple decoding procedures, this book takes an unusual turn. The standard approach would be to move on from there and introduce either more theory or present standard constructions of codes. The approach taken here is different.

A new starting-point and a new method are requisite, to insure a complete [classi?cation of the Steiner triple systems of order 15]. This method was furnished, and its tedious and di?cult execution und- taken, by Mr. Cole. F. N. Cole, L. D. Cummings, and H. S. White (1917) [129] The history of classifying combinatorial objects is as old as the history of the objects themselves. In the mid-19th century, Kirkman, Steiner, and others became the fathers of modern combinatorics, and their work – on various objects, including (what became later known as) Steiner triple systems – led to several classi?cation results. Almost a century earlier, in 1782, Euler [180] published some results on classifying small Latin squares, but for the ?rst few steps in this direction one should actually go at least as far back as ancient Greece and the proof that there are exactly ?ve Platonic solids. One of the most remarkable achievements in the early, pre-computer era is the classi?cation of the Steiner triple systems of order 15, quoted above. An onerous task that, today, no sensible person would attempt by hand calcu- tion. Because, with the exception of occasional parameters for which com- natorial arguments are e?ective (often to prove nonexistence or uniqueness), classi?cation in general is about algorithms and computation.

This book provides a quick access to computational tools for algebraic geometry, the mathematical discipline which handles solution sets of polynomial equations. Originating from a number of intense one week schools taught by the authors, the text is designed so as to provide a step by step introduction which enables the reader to get started with his own computational experiments right away. The authors present the basic concepts and ideas in a compact way.

One of the most remarkable and beautiful theorems in coding theory is Gleason's 1970 theorem about the weight enumerators of self-dual codes and their connections with invariant theory.

The algorithmic problems of real algebraic geometry such as real root counting, deciding the existence of solutions of systems of polynomial equations and inequalities, finding global maxima or deciding whether two points belong in the same connected component of a semi-algebraic set appear frequently in many areas of science and engineering. In this textbook the main ideas and techniques presented form a coherent and rich body of knowledge.Mathematicians will find relevant information about the algorithmic aspects. Researchers in computer science and engineering will find the required mathematical background.Being self-contained the book is accessible to graduate students and even, for invaluable parts of it, to undergraduate students.This second edition contains several recent results, on discriminants of symmetric matrices, real root isolation, global optimization, quantitative results on semi-algebraic sets and the first single exponential algorithm computing their first Betti number.

The appearance of this volume celebrates the ?rst decade of Magma, a new computeralgebrasystemlaunchedattheFirstMagmaConferenceonCom- tational Algebra held at Queen Mary and West?eld College, London, August 1993. This book introduces the reader to the role Magma plays in advanced mathematical research. Each paper examines how the computer can be used to gain insight into either a single problem or a small group of closely related problems. The intention is to present su?cient detail so that a reader can (a), gain insight into the mathematical questions that are the origin of the problems,and(b),developanunderstandingastohowsuchcomputations are speci?edinMagma.Itishopedthatthereaderwillcometoarealisationofthe important rolethatcomputational algebracanplayinmathematical research. Readers not primarily interested in using Magma will easily acquire the skills needed to undertake basic programming in Magma, while experienced Magma users can learn both mathematics and advanced computational methods in areas related to their own. The core of the volume comprises 14 papers. The authors were invited to submit articles on designated topics and these articles were then reviewed by referees. Although by no means exhaustive, the topics range over a consid- ablepartofMagma’scoverageofalgorithmicalgebra:fromnumbertheoryand algebraicgeometry,viarepresentationtheoryandcomputationalgrouptheory to some branches of discrete mathematics and graph theory. The papers are preceded by an outline of the Magma project, a brief summary of the papers and some instructions on reading the Magma code. A basic introduction to the Magma language is given in an appendix. Theeditorsexpresstheirgratitudetothecontributorstothisvolume,both for the work put into producing the papers and for theirpatience.

The theory of polynomials constitutes an essential part of university of algebra and calculus. Nevertheless, there are very few books entirely devoted to this theory. This book provides an exposition of the main results in the theory of polynomials, both classical and modern. Many of the modern results have only been published in journals so far. Considerable attention is given to Hilbert's 17th problem on the representation of non-negative polynomials by the sums of squares of rational functions and its generalizations. Galois theory is discussed primarily from the point of view of the theory of polynomials, not from that of the general theory of fields and their extensions.

This book presents algorithmic tools for algebraic geometry and experimental applications of them. It also introduces a software system in which the tools have been implemented and with which the experiments can be carried out. Macaulay 2 is a computer algebra system devoted to supporting research in algebraic geometry, commutative algebra, and their applications. The reader of this book will encounter Macaulay 2 in the context of concrete applications and practical computations in algebraic geometry. The expositions of the algorithmic tools presented here are designed to serve as a useful guide for those wishing to bring such tools to bear on their own problems. These expositions will be valuable to both the users of other programs similar to Macaulay 2 (for example, Singular and CoCoA) and those who are not interested in explicit machine computations at all. The first part of the book is primarily concerned with introducing Macaulay2, whereas the second part emphasizes the mathematics.

From the reviews of the 1st edition:"This book provides a comprehensive and detailed account of different topics in algorithmic 3-dimensional topology, culminating with the recognition procedure for Haken manifolds and including the up-to-date results in computer enumeration of 3-manifolds. Originating from lecture notes of various courses given by the author over a decade, the book is intended to combine the pedagogical approach of a graduate textbook (without exercises) with the completeness and reliability of a research monograph…All the material, with few exceptions, is presented from the peculiar point of view of special polyhedra and special spines of 3-manifolds. This choice contributes to keep the level of the exposition really elementary. In conclusion, the reviewer subscribes to the quotation from the back cover: "the book fills a gap in the existing literature and will become a standard reference for algorithmic 3-dimensional topology both for graduate students and researchers". Zentralblatt für Mathematik 2004For this 2nd edition, new results, new proofs, and commentaries for a better orientation of the reader have been added. In particular, in Chapter 7 several new sections concerning applications of the computer program "3-Manifold Recognizer" have been included.

The book deals with algorithmic problems related to binary quadratic forms. It uniquely focuses on the algorithmic aspects of the theory. The book introduces the reader to important areas of number theory such as diophantine equations, reduction theory of quadratic forms, geometry of numbers and algebraic number theory. The book explains applications to cryptography and requires only basic mathematical knowledge. The author is a world leader in number theory.

This is a textbook for a course (or self-instruction) in cryptography with emphasis on algebraic methods. The first half of the book is a self-contained informal introduction to areas of algebra, number theory, and computer science that are used in cryptography. Most of the material in the second half - "hidden monomial" systems, combinatorial-algebraic systems, and hyperelliptic systems - has not previously appeared in monograph form. The appendix by Menezes, Wu, and Zuccherato gives an elementary treatment of hyperelliptic curves. This book is intended for graduate students, advanced undergraduates, and scientists working in various fields of data security.

This book arose from a series of courses on computer algebra which were given at Eindhoven Technical University. Its chapters present a variety of topics in computer algebra at an accessible (upper undergraduate/graduate) level with a view towards recent developments. For those wanting to acquaint themselves somewhat further with the material, the book also contains seven 'projects', which could serve as practical sessions related to one or more chapters. The contributions focus on topics like Grobner bases, real algebraic geometry, Lie algebras, factorisation of polynomials, integer programming, permutation groups, differential equations, coding theory, automatic theorem proving, and polyhedral geometry. This book is a must-read for everybody interested in computer algebra.

In recent years, new algorithms for dealing with rings of differential operators have been discovered and implemented. A main tool is the theory of Grobner bases, which is reexamined here from the point of view of geometric deformations. Perturbation techniques have a long tradition in analysis; Grobner deformations of left ideals in the Weyl algebra are the algebraic analogue to classical perturbation techniques. The algorithmic methods introduced here are particularly useful for studying the systems of multidimensional hypergeometric PDEs introduced by Gelfand, Kapranov and Zelevinsky. The Grobner deformation of these GKZ hypergeometric systems reduces problems concerning hypergeometric functions to questions about commutative monomial ideals, and leads to an unexpected interplay between analysis and combinatorics. This book contains a number of original research results on holonomic systems and hypergeometric functions, and raises many open problems for future research in this area.