NDLI: On using bi-equational constraints in CAD construction

Please wait, while we are loading the content...

A view on the future of symbolic computation

D-finiteness: algorithms and applications

On a finite kernel theorem for polynomial-type optimization problems and some of its applications

Gosper's algorithm, accurate summation, and the discrete Newton-Leibniz formula

Signature of symmetric rational matrices and the unitary dual of lie groups

Sum of roots with positive real parts

Algebraic general solutions of algebraic ordinary differential equations

Adherence is better than adjacency: computing the Riemann index using CAD

Fast algorithms for polynomial solutions of linear differential equations

Non complete integrability of a magnetic satellite in circular orbit

Symmetric and semisymmetric graphs construction using G-graphs

Picard--Vessiot extensions for linear functional systems

On using bi-equational constraints in CAD construction

Hybrid symbolic-numeric integration in multiple dimensions via tensor-product series

A BLAS based C library for exact linear algebra on integer matrices

Structure and asymptotic expansion of multiple harmonic sums

Lifting techniques for triangular decompositions

Computing the multiplicity structure in solving polynomial systems

Algorithms for the non-monic case of the sparse modular GCD algorithm

Computing μ-bases of rational curves and surfaces using polynomial matrix factorization

Efficient computation of the characteristic polynomial

Selfintersections of a bézier bicubic surface

A procedure for proving special function inequalities involving a discrete parameter

Generalized Loewy-decomposition of d-modules

On computing nearest singular hankel matrices

A reliable block Lanczos algorithm over small finite fields

Schur partition for symmetric ternary forms and readable proof to inequalities

Affine transformations of algebraic numbers

Architecture-aware classical Taylor shift by 1

On the complexity of factoring bivariate supersparse (Lacunary) polynomials

Generic matrix multiplication and memory management in linBox

Exact analytical solutions to the nonlinear Schrödinger equation model

Half-GCD and fast rational recovery

Application of Wu's method to symbolic model checking

Probabilistic algorithms for computing resultants

Generalized normal forms and polynomial system solving

Domains and expressions: an interface between two approaches to computer algebra

Symbolic-numeric completion of differential systems by homotopy continuation

Algorithms for symbolic/numeric control of affine dynamical systems

Finding telescopers with minimal depth for indefinite nested sum and product expressions

Multivariate power series multiplication

Partial degree formulae for rational algebraic surfaces

Computing the rank and a small nullspace basis of a polynomial matrix

Approximation of dynamical systems using s-systems theory: application to biological systems

Generalized laplace transformations and integration of hyperbolic systems of linear partial differential equations

Preconditioners for singular black box matrices

Solving second order linear differential equations with Klein's theorem

Deterministic equation solving over finite fields

Stability analysis of biological systems with real solution classification

An open problem on metric invariants of tetrahedra

Admissible orderings and finiteness criteria for differential standard bases

On using bi-equational constraints in CAD construction

Content Provider	ACM Digital Library
Author	McCallum, Scott Brown, Christopher W.
Abstract	This paper introduces an improved method for constructing cylindrical algebraic decompositions (CADs) for formulas with two polynomial equations as implied constraints. The fundamental idea is that neither of the varieties of the two polynomials is actually represented by the CAD the method produces, only the variety defined by their common zeros is represented. This allows for a substantially smaller projection factor set, and for a CAD with many fewer cells.In the current theory of CADs, the fundamental object is to decompose n-space into regions in which a polynomial equation is either identically true or identically false. With many polynomials, one seeks a decomposition into regions in which each polynomial equation is identically true or false independently. The results presented here are intended to be the first step in establishing a theory of CADs in which systems of equations are fundamental objects, so that given a system we seek a decomposition into regions in which the system is identically true or false --- which means each equation is no longer considered independently. Quantifier elimination problems of this form (systems of equations with side conditions) are quite common, and this approach has the potential to bring large problems of this type into the scope of what can be solved in practice. The special case of formulas containing two polynomial equations as constraints is an important one, but this work is also intended to be extended in the future to the more general case.
Starting Page	76
Ending Page	83
Page Count	8
File Format	PDF
ISBN	1595930957
DOI	10.1145/1073884.1073897
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-07-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Cad Polynomial systems
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in