Significant progress has been made during the last 15 years in the solution of nonlinear systems, particularly in computing fixed points, solving systems of nonlinear equations and applications to equilibrium models.

One service methematics has rendered 'Et moi, ... , si j'avait su comment en revenir, je n'y serais point alle.' the human race. It has put common sense JulesVerne back where it belongs, on the topmost shelf next to the dusty canister labelled The series is divergent; therefore we may 'discarded nonsecse'. be able to do something with it. Eric T. Bell O.Heaviside Mathematics is a tool for thought. A highly necessary tool in a world where both feedback and nonlinearities abound. Similarly, all kinds of parts of mathematics serve as tools for other parts and for other sciences. Applying a simple rewriting rule to the quote on the right above one finds such statements as: 'One service topology has rendered mathematical physics ... '; 'One service logic has rendered computer science ... '; 'One service category theory has rendered mathematics ... '. All arguable true. And all statements obtainable this way form part of the raison d'etre of this series.

This volume considers the computational complexity of determining whether a system of equations over a fixed algebra A has a solution. It examines in detail the two problems this leads to: SysTermSat(A) and SysPolSat(A), in which equations are built out of terms or polynomials, respectively. The book characterizes those algebras for which SysPolSat can be solved in a polynomial time. So far, studies and their outcomes have not covered algebras that generate a variety admitting type 1 in the sense of Tame Congruence Theory. Since unary algebras admit only type 1, this book focuses on these algebras to tackle the main problem. It discusses several aspects of unary algebras and proves that the Constraint Satisfaction Problem for relational structures is polynomially equivalent to SysTermSat over unary algebras. The book’s final chapters discuss partial characterizations, present conclusions, and describe the problems that are still open.

Analytic Computational Complexity contains the proceedings of the Symposium on Analytic Computational Complexity held by the Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pennsylvania, on April 7-8, 1975. The symposium provided a forum for assessing progress made in analytic computational complexity and covered topics ranging from strict lower and upper bounds on iterative computational complexity to numerical stability of iterations for solution of nonlinear equations and large linear systems. Comprised of 14 chapters, this book begins with an introduction to analytic computational complexity before turning to proof techniques used in analytic complexity. Subsequent chapters focus on the complexity of obtaining starting points for solving operator equations by Newton's method; maximal order of multipoint iterations using n evaluations; the use of integrals in the solution of nonlinear equations in N dimensions; and the complexity of differential equations. Algebraic constructions in an analytic setting are also discussed, along with the computational complexity of approximation operators. This monograph will be of interest to students and practitioners in the fields of applied mathematics and computer science.

The algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century that metamathematical problems have led to the intensive search for a precise and sufficiently general formalization of the notions of computability and algorithm. In the 1930s, a number of quite different concepts for this purpose were pro posed, such as Turing machines, WHILE-programs, recursive functions, Markov algorithms, and Thue systems. All these concepts turned out to be equivalent, a fact summarized in Church's thesis, which says that the resulting definitions form an adequate formalization of the intuitive notion of computability. This had and continues to have an enormous effect. First of all, with these notions it has been possible to prove that various problems are algorithmically unsolvable. Among of group these undecidable problems are the halting problem, the word problem theory, the Post correspondence problem, and Hilbert's tenth problem. Secondly, concepts like Turing machines and WHILE-programs had a strong influence on the development of the first computers and programming languages. In the era of digital computers, the question of finding efficient solutions to algorithmically solvable problems has become increasingly important. In addition, the fact that some problems can be solved very efficiently, while others seem to defy all attempts to find an efficient solution, has called for a deeper under standing of the intrinsic computational difficulty of problems.

The subject of this book is the solution of polynomial equations, that is, s- tems of (generally) non-linear algebraic equations. This study is at the heart of several areas of mathematics and its applications. It has provided the - tivation for advances in di?erent branches of mathematics such as algebra, geometry, topology, and numerical analysis. In recent years, an explosive - velopment of algorithms and software has made it possible to solve many problems which had been intractable up to then and greatly expanded the areas of applications to include robotics, machine vision, signal processing, structural molecular biology, computer-aided design and geometric modelling, as well as certain areas of statistics, optimization and game theory, and b- logical networks. At the same time, symbolic computation has proved to be an invaluable tool for experimentation and conjecture in pure mathematics. As a consequence, the interest in e?ective algebraic geometry and computer algebrahasextendedwellbeyonditsoriginalconstituencyofpureandapplied mathematicians and computer scientists, to encompass many other scientists and engineers. While the core of the subject remains algebraic geometry, it also calls upon many other aspects of mathematics and theoretical computer science, ranging from numerical methods, di?erential equations and number theory to discrete geometry, combinatorics and complexity theory. Thegoalofthisbookistoprovideageneralintroduction tomodernma- ematical aspects in computing with multivariate polynomials and in solving algebraic systems.

This book contains a collection of survey papers in the areas of algorithms, lan guages and complexity, the three areas in which Professor Ronald V. Book has made significant contributions. As a fonner student and a co-author who have been influenced by him directly, we would like to dedicate this book to Professor Ronald V. Book to honor and celebrate his sixtieth birthday. Professor Book initiated his brilliant academic career in 1958, graduating from Grinnell College with a Bachelor of Arts degree. He obtained a Master of Arts in Teaching degree in 1960 and a Master of Arts degree in 1964 both from Wesleyan University, and a Doctor of Philosophy degree from Harvard University in 1969, under the guidance of Professor Sheila A. Greibach. Professor Book's research in discrete mathematics and theoretical com puter science is reflected in more than 150 scientific publications. These works have made a strong impact on the development of several areas of theoretical computer science. A more detailed summary of his scientific research appears in this volume separately.

These days, computer-based simulation is considered the quintessential approach to exploring new ideas in the different disciplines of science, engineering and technology (SET). To perform simulations, a physical system needs to be modeled using mathematics; these models are often represented by linear time-invariant (LTI) continuous-time (CT) systems. Oftentimes these systems are subject to additional algebraic constraints, leading to first- or second-order differential-algebraic equations (DAEs), otherwise known as descriptor systems. Such large-scale systems generally lead to massive memory requirements and enormous computational complexity, thus restricting frequent simulations, which are required by many applications. To resolve these complexities, the higher-dimensional system may be approximated by a substantially lower-dimensional one through model order reduction (MOR) techniques. Computational Methods for Approximation of Large-Scale Dynamical Systems discusses computational techniques for the MOR of large-scale sparse LTI CT systems. Although the book puts emphasis on the MOR of descriptor systems, it begins by showing and comparing the various MOR techniques for standard systems. The book also discusses the low-rank alternating direction implicit (LR-ADI) iteration and the issues related to solving the Lyapunov equation of large-scale sparse LTI systems to compute the low-rank Gramian factors, which are important components for implementing the Gramian-based MOR. Although this book is primarly aimed at post-graduate students and researchers of the various SET disciplines, the basic contents of this book can be supplemental to the advanced bachelor's-level students as well. It can also serve as an invaluable reference to researchers working in academics and industries alike. Features: Provides an up-to-date, step-by-step guide for its readers. Each chapter develops theories and provides necessary algorithms, worked examples, numerical experiments and related exercises. With the combination of this book and its supplementary materials, the reader gains a sound understanding of the topic. The MATLAB® codes for some selected algorithms are provided in the book. The solutions to the exercise problems, experiment data sets and a digital copy of the software are provided on the book's website; The numerical experiments use real-world data sets obtained from industries and research institutes.