CaminoReal Notes Dennis Arnon c Copyright 1986 Xerox Corporation. All rights reserved. I. Documentation facilities User interface for expressions to/from Tioga docs Look at how EditTool implements character artwork manipulation. Look at TiogaAccess, TiogaOps (for locking) interfaces. Should be able to select an expr in a doc, find out its domain, operate on it, or get it into a Camino viewer for editing. Revision of Meddle internal rep - should contain, separately, the mathematical content of the expr, domain info, and formatting info. All stored with an expression put in a doc, and recursively, in some sensible way, for subexpressions. This may require revision of AlgebraStructures reps, e.g. the exponent of a variable in a polynomial should be selectable, and should carry full content, domain, and formatting info. Need language for expressing domains, so can to/from Rope. Put Tioga level structure on an expression in a doc. Cf. Peanut. Linebreaking for exprs in docs. Anything to be learned/lifted from TiogaImager? Camino Viewer glitches. Defaultly scale Camino viewer to be just tall enough to hold expression in it, and automatic legible positioning of expr in new viewer (i.e. home the result of an operation). Fix erroneous persistence of old stuff when viewer repainted. Faster repainting Store interpress fragment with a MeddleExpr node? Incremental repaint algorithm? Viewers into docs (Fournier) Have an interactive viewer tool in the document when it comes up on the screen. Some rule for painting that space when you print the doc. Maybe could be done hacking artwork nodes. Math expressions into slides There should be an easy way to do it. Programmable documents E.g. an expression can be specified as the derivative of some previous expression. Randy Frank's example: an expression is a self-contained program, e.g. you set A and B to something, then render SQRT(A^2 + B^2 + A + B). Schelter - when you have such computed expressions, you don't want to recompute them everytime you run off the document, only when necessary. This should perhaps be managed by "version control" among the expressions in a doc, so that if you change an expr that another expr is computed from, that other expr will recompute itself next time you repaint the screen or run off the doc. Or if the computations are long, perhaps you want it to recompute itself in background with a slackprocess. Section numbering tools What section numbering tools does one want in WYSIWIG editor? Presumably there should be a property on the node that says - number it. Same question for Bibliography facilities, enumeration, etc. Integration with other Document Management tools Integration with Whiteboards? EditTool interface Replace EditTool with popup menus. Tioga -> TeX conversion Do it eventually so e.g. one can transmit a technical doc created with Tioga to another site. Note that having DVI -> IP would enable an emulation of the EXPRES Diamond -> TeX -> Postscript pipeline with a Tioga -> TeX -> Interpress pipeline. II. General algebra environment Integer arithmetic, quotient constructor. Combiner uses CaminoReal. Separate BigRats for CedarChest like BigCardinals, not AlgebraStructures? Spreitzer tip table extensions Also move around in the tree structure from the keyboard (e.g. ^Q to move to sibling) New Domains Vector type: Use it or point or sequence for RatIntervals, Variables. EquationsOver, RelationsOver (similar to FormulasOver). Add existential, universal quantifiers. Chat interface to Vaxc algebra systems Basic facility - I give the command to invoke on the remote machine, the file of data to pass to it, and a filename where the output is supposed to be stored. Execution of the command on the remote command creates a tempfile on there, which is then pupftp'd over to the specified filename in the Cedar system. I also specify in what way, if at all, I want to wait for that computation to complete. RPC to Vax? How does Chat do it? Distributed computation Use of the Summoner. This is actually a gateway to distributed computations in multiple environments eg. through Chat interface to Vax. Issue is what alternatives for use of distributed computing facilities are to be provided? Can a distributed computation, including specification for partitioning, i.e. "parallelization", of an algorithm, be invoked on the fly, or does the client have to sit down and specify a fixed partitioning of the algorithm in advance? What should it be? The FutureValue construct (Schelter ref to Halstead@MIT). Should mesh with chatting to remote algebra systems. Sample problem to try: determinant expansion by minors. User interface re: lightweight and heavyweight computations When a user forks a remote computation, maybe should specify whether he wants to wait for it. If not, has to specify what it should do. E.g. if I fork a ray tracing, what is it supposed to do? History mechanism, and referring to previous objects/expressions Scrollable history document? Need ability to refer to name objects and/or expressions, and refer to them in future objects/expressions by name. The question is: what is Iris's history mechanism, and what is it's ability to delve into existing databases of expressions? What is Views? Extensibility issues How should users specify new operators, or new domains? Need to specify things like canonical forms, formatting rules for legal expressions. Recast (conversion) issues Automatic conversion where appropriate, or tell user to modify domain if he want that op? How hard is automatic domain inference for an arbitrary expression (Scott Morrison)? Programming Language issues, interface to other algebra systems Fateman says he wants at least ability to enter commands from keyboard. Doable with Cedar interpreter? CNTRL-E (Cedar abbreviations) facility from keyboard. Soiffer's idea of Reduce parser inside the interface. Ergonomics of large expressions Level clipping, or better, close up levels and show an icon. Run Magnifier over large expression. Fisheye views (George Furnas). Alison Lee - space invader icons. Access to remote computational resources Managing suites of Vax software from Cedar Matching directory structures, edit with Tioga, RemoteCompile and SystemBuild commands. Thus we never have to think about what is actually happening on the Vax. Extension of DF file mechanism to verify that things built successfully on Vax, i.e. that software there is in a good state. Unix Contributed Software standards for package maintenance? General issues What are you to be allowed to do on the remote system? Pass programs? Interrupts? SAC-2 on Vax Listing of some supported commands (e.g. DoCad, FactorPolynomial) in SAC-2 and how you access them. Facility for writing, compiling, running an Aldes/SAC-2 program under CaminoReal. Standard interchange format for files of cad information Access to Lisp machines at PARC Can a single paradigm suffice to access Macsyma both on Vax and on Lisp machines? RPC interface to Reduce in Interlisp. Running Cedar and Lisp in separate partitions on the same Dorado, communication by files (Bobrow). Common microcode project (Bobrow). Remote procedure call. Examples of useful Interlisp facilities are - Notecards, Argnoter, Cognoter. People who have built connections between Cedar and Interlisp: Swinehart (see Yearend report), Russ, Bobrow. Foster - RPC (Henry Thompson's) takes 100 ms in InterLisp, 10ms in Cedar. (- that's the RPC from one Cedar machine to another? How long does it take for the dictionary server?) In his COLAB work they have the ability to move mouse across different machines. Foster - There is a FORMAX? layout program in Interlisp, which can be used as part of Tedit. III. Plotting. We deal in abstract, symbolic, exact mathematical objects. Approximations to them, covering set files, pictures of them, are all approximations to the abstract entity. Thus anything to be plotted must be an abstract object belonging to some mathematical domain. "Plot" is a method which an object may have. Plotting contexts are objects; come in 2D and 3D flavors. In CaminoReal, a plotting context is instantiated as a Viewer. IV. Cedar cad implementation Review of the AlgebraStructures computer algebra system New operations Request for any AlgebraicSurfaces display op starts up the tool if not already started. Or have it running all the time, and each display request creates a new surfaceDisplay viewer. AlgebraClasses has proc to add an op to a structures property list. Or MakeSequenceStructure proc takes procs to add to prop list as args. Cad ops induced cad Alternate display showTriangulationAll (valid only for cad's of 1-, 2- and 3-space) showTriangulationSections showTriangulation0Cells showTriangulation1Cells showTriangulation2Cells rayTraceInputPolynomials (valid only for cad's of 3-space) show cells show statistics Cad's should have names, statistics Store only basis signatures with cells. Both clustering during cad construction, and clustering for disambiguation of signatures, are done with basis signatures (if basis signatures with ordinary projections don't suffice to get unambiguous clusters, then we have to go back and refine cad with respect to augmented projections). Cluster ops select containing cad rayTrace (valid only for 2-cluster in 3-space) showTriangulation (valid only for clusters in cad's of 1-, 2- and 3-space) Cell ops select containing cad rayTrace (valid only for 2-section in 3-space) showTriangulation (valid only for cells in cad's of 1-, 2- and 3-space) Polynomial sequence ops, for base coeffs that are ints or bigrats rayTraceZeros (valid only 3-variate polys) decomposeZeros (forks Vax computation; pop up menu for options (including covering set parameters); inserts cad in Active MessageSet) showZerosTriangulation (valid only for 1-, 2- and 3-variate polys) New Polynomial ops, for base coeffs that are ints or bigrats rayTrace (valid only for 3-variate poly) decomposeZeros (forks Vax computation; pop up menu for options (including covering set parameters); inserts cad in Active MessageSet) showZeroTriangulation (valid only for 1-, 2- and 3-variate poly) Sequences Basic display is one line: "sequence of n shortPNames" Alternate display: Slider bar onto popup menu popup menu entries are shortPNames of sequence elements Insert creates a blank entry in popup menu; then select item to be inserted as an operand, it is type checked, inserted. Delete modifies pop up menu Selection of Insert or Delete forces Alternate display Adjacencies and Clusters, Graph ops, read adjacencies, compute clusters We have made a basic decision to go with basis signatures. First step is the current "cells with signature" op. This assumes that every cell in the cad has a basis signature, then this is a binary op that takes a legal (i.e. correct length) basis signature (perhaps with * elements) and returns a sequence of cells with that sig. ExtractClusters: PROC [cad: Cad, numComponents: CARDINAL] RETURNS [clusters: SEQ.Sequence]; AdjacenciesOverAdjacency: PROC [dimension: CARDINAL, adjacency: Adjacency, cad: Cad] RETURNS [newAdjacencies: LIST OF Adjacency]; Cad statistics records SmartInfo about the cad (0-cell bounding box, singularities, turning points). New cell Ops: read covering set, display covering set 2D display improvements Use adjacencies for continuous (no big 0-cells) display of curves. Display of open, closed 2-cells. Eliminate use of df's in cell display? 3D display improvements Merge in Rauen's tool (changes to ThreeDWorld format). Need to normalize forward and up vectors? Why does Rauen have to read files? Why does he need his own internal form? Use Jules' Geometry3DApplied interface. Offer wireframes. Maureen's color solid viewing tools. Giordano's assertion of the three standard, plus a certain perspective view, as giving intuition. Rauen has alg to determine what cells a ray hits? Would be a good op to offer in interface, i.e. what cells would I see if I had xray vision? Vuillemin - draw in axes on request. How do you come up with a good triangulation? How to have a good algorithm which both may, and may not, take account of adjacency information? Steps by which Rauen takes a triangulation and renders it. Eliminate use of df's in cell display? User interface Mode: Topology-priority (faster) vs. Shape-priority (slower) User selects whether he is more concerned with rapid real-time interaction in which the only constraint is to show topology accurately, or with beautiful pictures that show the true shape of objects. Mode: Smooth vs. Structural User selects whether to have the individual cells "glued together", in order to see smooth objects, or whether to see the individual cells. In the latter case, 0-cells are expanded into fat balls and 1-cells are fattened into "wires". An interesting special case of this mode is displays of entire cad's. A cad is just a particular cell decomposition of the line, plane, or all space. If the user selects geometry mode, we just see some indication that the displayed set is the entire line, plane, or space. In structure mode, we see the individual cells of the cad. A simple initial interface for surface display The user gives a trivariate polynomial, which we interpret as a surface to be displayed, and a bounding box. A cad (for the surface and bounding box), and a triangulation of each positive dimensional cell, is done on Vaxc and written to a file, which includes a specification of which cells comprise the portion of the surface in the bounding box. The display tool reads the file. Initially there are two kinds of display available: a topology-priority, structural mode (done by displaying the triangulations of the cells which comprise the surface), and a shape-priority, smooth mode (done by ray tracing the surface defining equation directly). Someone (it is unspecified who) may crawl over triangulations in an effort to "topologically optimize" them, i.e. to get by with as few polygons as possible while still guaranteeing the topological correctness of any collection of cells. At this level there are no handles on individual cells. You can only display the entire portion of the surface in the bounding box. Next stage: ray tracing 2-cells contained in surfaces Now cad files are required to contain some kind of defining formula for each 2-cell, the format of which has been negotiated. The requirement is that the ray tracer has to be able to use it in order to ray trace individual 2-cells. Ideally, the ray tracer should be able to work with the "glued-together" quantifier-free formulas of a cluster of cells. Thus we should be able to have a shape-priority, structural mode for a collection of cells lying in a surface, in which we see all the different cells and 2-cells are individually ray traced, or a shape-priority, smooth mode for a subset of surface, in which we display the union of all the cells in a smooth fashion. Now the display tool should now show the indices of all the cells currently being displayed, and allow the user to add and delete cells named by index. Future user action: define a semi-algebraic set to display As mentioned, in every display situation we have particular sets of polynomials, and a cad for those sets. The display tool assigns names to these polynomials, say A, B, ... The user is then able to write any valid quantifier-free formula using these names, e.g. "$A = 0~AND~B < 0$", or "$A = 0~\Rightarrow~B < 0$" The display tool determines the cells satisfying this formula (i.e. the cells comprising the semi-algebraic set defined by that formula), and displays them in the current display mode(s). Future user action: Pointing at cells It would be nice if the user could point, or otherwise indicate, particular cells to be deleted or added to the display. AlgebraStructures Rootfinder, new cell op: generate covering set Partititioning the cad algorithm The idea is to define interfaces between different parts of the algorithm, and identify things that can be done in parallel. The interfaces should consist of data to be passed; for each such dataset there should be a file format so the computation can be done on different machines. Compute and add adjacencies to an existing cad in Cedar Do we want to separate adjacency computation from cad computation? If so, set up a SAC-2 routine to do it; allow ComputeServer to queue up a succession of jobs, to be done in background. Step two: implement the computation in Cedar. 2D case first. Organizing SAC-2 cad software Collect McCallum, G-basis packages, make available through appropriate commands. Organize and make portable like any other Unix software. User manual? Plan use of other resources such as Delaware IBM, Ohio-State machines. Cad databases At the moment all we can do is read/write entire cads from a file. A database of cad's is just a bunch of files in a directory. A database of such files should be stored on Cyan. The format should be such that it can be read/written by both Cedar and Vax. There should be a format that includes all info - cad, adjacencies, covering sets. Also need a good way of keeping statistics on various parts of the computation. Reading such files is slow. Need command to read some more cells of this cad and add them to the database. Cypress database? Once have distributed computations, we want to be able to do incremental updates of the database. This is a great example for implementing cad computation related stuff in Cedar by forking off appropriate subcommands to remote SAC-2 systems. RefineCad: PROC [inCad: Cad, refiningPoly: Polynomial, cellsToRefine: Sequence] RETURNS [outCad: Cad]; CoarsestSqFreeBasis: PROC [inputPolynomials: SEQ.Sequence, localizationFormula: QFF.Formula _ NIL] RETURNS [contents, basis: SEQ.Sequence]; Projection: PROC [basis: SEQ.Sequence] RETURNS [basisProjection: SEQ.Sequence]; BasePhase: PROC [cad: Cad]; RegionExtendCadToCad: PROC [cad: Cad]; ExtendRegionToCells: PROC [dimension: CARDINAL, region: SignedRegion, cad: Cad] RETURNS [newCells: SEQ.Sequence]; ExtendCellToStacks: PROC [i: CARDINAL, cell: Cells.Cell, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; ExtendStacksToStacks: PROC [i: CARDINAL, StacksInEiM1: SEQ.Sequence, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; QE phase MakeQEProblem: PROC [inputFormula: QFF.Formula, localizationFormula: QFF.QFFormula, inputVariables: VARS.VariableSeq, minPolyVariable: VARS.VariableSeq _ AN.defaultMinPolyVariable, fieldElementVariable: VARS.VariableSeq _ RF.defaultFieldElementVariable] RETURNS [QET.QEProblem]; EliminateQuantifiers: PROC [QET.QEProblem]; EliminateInnermostQuantifier: PROC [StacksInEr: QET.StackSeq, formula: QFF.Formula]; EliminateInnerQuantifier: PROC [i: CARDINAL, StacksInEi, StacksInEiM1: QET.StackSeq, formula: QFF.Formula]; Simplifier The basic strategy is to assume clusters in r-space invariant with respect to bases in all dimensions. No effort to separate complete factors of input polynomials from factors of projection polynomials. If we have unambiguous signatures at this point, then we just have to simplify. If not, we have to refine the cad with respect to augmented projections and get clusters invariant with respect to these new larger bases in each dimension. Having done this we know we'll get unambiguous clusters. DisambiguateSignatureTable: PROC [inTable: QET.SignatureTable] RETURNS [outTable: QET.SignatureTable]; SimplifySignatureSeq: PROC [QET.SignatureSeq] RETURNS [QET.SignatureSeq]; SignatureSeqToFormula: PROC [QET.SignatureSeq] RETURNS [QFF.QFFormula]; Actually is an op on a set of polys so that we end up with a decomposition which is cylindrical with respect to two coordinate systems. Application of Cedar cad algorithm 1. Demonstrate topologically reliable display of algebraic and parametric curves and surfaces, and display of fat plane and space curves. 2. Application of distributed cad algorithm to qe problems involving roots of quartic polynomials (full Kahan ellipse, root configuration-coefficient classification for quartics) 3. Study of parametric curves and surfaces: spline analyzer, spline combiner. Expert system for directing problem solving by cad computation Has the knowledge base of info about root configuration from evaluation of coefficients. Tries heuristics, e.g. detecting common zeros by Grobner basis computation. Knows what computations to do to build a sufficient database for solving the qe or decision problem. V. Lisp interoperability. CommonLisp Macsyma Issues for interoperability with Lisp software RPC interface to Reduce in Interlisp. Running Cedar and Lisp in separate partitions on the same Dorado, communication by files (Bobrow). Common microcode project (Bobrow). Remote procedure call. Examples of useful Interlisp facilities are - Notecards, Argnoter, Cognoter. People who have built connections between Cedar and Interlisp: Swinehart (see Yearend report), Russ, Bobrow. Foster - RPC (Henry Thompson's) takes 100 ms in InterLisp, 10ms in Cedar. (- that's the RPC from one Cedar machine to another? How long does it take for the dictionary server?) In his COLAB work they have the ability to move mouse across different machines. Foster - There is a FORMAX? layout program in Interlisp, which can be used as part of Tedit. What distributed computing facilities are available in the PARC Interlisp/CommonLisp world? E.g. even if one could marshall lots of DLions to run list, what is available to make them play together? Initial hardware: Cedar on a DLIon controlling Lisp on a Dorado. Note: Kyoto CommonLisp + Mesa C compiler => Lisp -> Mesa translation facility? Other Lisp software 1. Chou software, G-basis software 2. Expert systems for geometric reasoning, math problem solving, blending numerical and scientific computation, selecting numerical algorithms in a polyalgorithm environment, assigning a domain to an arbitrary math expression (Scott Morrison), authoring. 3. Hook Notecards to Tioga docs? 4. Glisp algebra system, Glisp as database browser? CommonLoops algebra system? VI. Numerical software. Implementing it in Cedar vs. using it on other machines. Mimosa arithmetic. References [AND83] R. A{\small NDERSON}, {\sl EXED: A prototype user interface for algebraic manipulation systems}, Stanford University, MS., October 1983. [COW78] R. C{\small OWAN AND} M. G{\small RISS}, {\sl Towards an algebra system based on pattern matching}, Report UCP-67, University of Utah, Oct. 1978. [FIT82] J. F{\small ITCH AND} J. P{\small ADGETT}, {\sl A pure and really simple initial functional algebraic language}, Mathematics Unit, University of Bath, December 1982. [FOS84a] G. F{\small OSTER}, {\sl User interface considerations for algebraic manipulation systems}, Report No. UCB/CSD 84/192, EECS Dept., U.C. Berkeley, April 1984. [FOS84b] G. F{\small OSTER}, {\sl DREAMS: Display REpresentation for Algebraic Manipulation Systems}, Report No. UCB/CSD 84/193, EECS Dept., U.C. Berkeley, June 1984. [HEA80] A. H{\small EARN}, {\sl The personal algebra machine}, Proc. IFIP '80, North-Holland, Amsterdam, 1980, pp. 620-628. [JEN78] R. J{\small ENKS}, {\sl Towards a language for use and implementation of algebra systems}, Report UCP-64, Symbolic Computation Group, Comp. Sci. Dept., Univ. of Utah, April 1978, 20pp. [JEN80] R. J{\small ENKS}, {\sl MODLISP: A preliminary design}, Report RC8073, Math. Science Dept., IBM TJ Watson Research Center, Jan 18, 1980. [JEN81] R. J{\small ENKS}, {\sl A language for computational algebra}, Report RC8930, Math. Science Dept., IBM TJ Watson Research Center, July 14, 1981. [MAR80] J. M{\small ARTI}, {\sl Compilation techniques for a control-flow LISP system}, Proceedings of the LISP '80 Conference, 203-207. [MAF82] J. M{\small ARTI AND} J. F{\small ITCH}, {\sl The Bath Concurrent Lisp Machine}, Mathematics Unit, University of Bath, December 1982; Also Proc. EUROCAL '83? [MAR82] J. M{\small ARTI}, {\sl Interprocess comuunication in the Bath Multiple 68000}, Mathematics Unit, University of Bath, December 1982. [PAD82] J. P{\small ADGETT AND} J. F{\small ITCH}, {\sl A new model for dynamic access environments}, Mathematics Unit, University of Bath, December 1982. [SOI??] N. S{\small OIFFER}, {\sl A perplexed user's guide to Andante}, MS. U.C. Berkeley. [WAT85] S. W{\small ATT}, {\sl Parallel algorithms for computer algebra}, Ph.D., University of Waterloo, 1984. ACaminoRealNotes.tioga Dennis Arnon, October 13, 1986 12:52:18 pm PDT components assumed to be of cad, and not some induced cad thereof. Components: Menus.MenuProc = { User specifies polynomials with respect to which to cluster by (*,*,@,*,*,@) tuples (@ is new FormulaOperators.Op). edgePredicate: GraphOps.EdgePredicate ~ { cell1: QET.Cell _ NARROW[v.rep]; cell2: QET.Cell _ NARROW[w.rep]; RETURN[cell1.basisSignature.structure.class.equal[cell1.basisSignature, cell2.basisSignature] ]; }; inducedCad: QET.Cad _ QEIO.GetInducedCad[cad, dimension]; numComponents: CARDINAL _ GraphOps.DetermineComponents[cad.abstractGraph, Undirected, edgePredicate]; clusters: QET.SignedRegionSeq _ Cads.ExtractClusters[inducedCad, numComponents]; QEIO.WriteSignedRegionSeq[clusters, out]; }; MaximalSignedRegions: PROC [dimension: CARDINAL, cad: Cad, primary: BOOL]; Depth-First Search connected components computation in the dimension-space cad graph, filling in the (IF primary THEN primaryRegion ELSE secondaryRegion) fields of cells. ExtractSignedRegions: PROC [dimension: CARDINAL, cad: Cad, primary: BOOL] RETURNS [SEQ.Sequence]; Extract from the dimension-space cad graph, the (IF primary THEN primaryRegion ELSE secondaryRegion) cell-field-defined regions. For i = 2 or 3 only, returns all interstack adjacencies in i-space over an adjacency in dimension-1 space. cad is i-space cad. newAdjacencies = NIL if no adjacencies in dimension space can be built, either because needed auxiliary E^(i-1) cell-cell adjacencies, or non-NIL sample points, cannot be found. Converts extended to primitive sample points as needed. May build adjacencies over appropriate auxiliary E^(i-1) cell-cell adjacencies if necessary, and/or query i-space cad for existing adjacency information. RefineCad operation (Real algebraic variety Combiner) cellsToRefine is a set of cell indices. outCad is a refinement of inCad that is coarsest possible with respect to the property that each of the cells in cellsToRefine has been decomposed into refiningPoly-invariant cells. Implemented by rerunning the whole cad construction algorithm. Consider 1-space. Assume we have saved the isolated roots of the univariate basis that define the cells, and assume that there is only one cell c to refine, and suppose that the 1-space projection of c is a 1-cell, say the interval (a,b). We compute new projections all the way down by combining refiningPoly with existing polys. When we get to 1-space, we probably have some univariate polynomials that we didn't have before. We ask if any of these new polynomials have roots in (a,b). If so, then we break up (a,b) into new cells, and rebuild the cad from there. Finally we assign new cell indices where necessary. Projection Phase The requirements are: (1) we have a certain set K of polynomials in E^r which we need to make delineable on each cell and each signature-cluster in E^(r-1). (2) The collection of cells we end up with in E^r must have the boundary property: the boundary of any cell must equal the union of some collection of lower-dimensional cells. Question: why does the boundary property really matter? Possible answer: then it doesn't matter where you probe when slicing an adjacency. To be more precise, boundary property is required for the "decoding" phase of our (0,1) adjacency determination in 3-space to work - we have to know that the 0-cells we see in our 2-space projection are images of 0-cells in the 3-space decomposition. Given these, our approach is: (1) Compute contents and basis(pp) = K of inputs, pull off initial sequences of non-constant coeffs of all basis elts, compute basis for contents union initial sequences, do a signature-invariant decomp D of E^(r-1) to get regions on which each element of K has constant degree. Note that if any element of K is identically zero at some point of E^r-1, D will have maximal regions for this property. (2) using the appropriate reducta of elements of K (ignore identically zero elements), compute projection sets for each reducta pattern that occurs on a positive-dimensional regions, compute basis. For each positive-dimensional region, use this basis to break it up to be signature-invariant with respect to its projection basis. We end up with a new decomposition D'. (3) Assume now r <= 3; maybe works for general r. (4) On each region in E^(r-1), evaluate the appropriate non-identically zero reducta of elements of K to get a set of algebraic polys; compute its basis. If any element of K is identically zero on this region, determine the appropriate algebraic polynomials whose roots we need to take account of to insure boundary property, compute their basis, merge the two bases. Isolate roots of the final basis to determine the stack over this region. Simpler version, to get a single basis set in each E^i, which we want in order to be able to say very simply what clusters we have (namely: invariant with respect to the bases in all dimensions): (1) Compute P1 = contents and K = basis(pp) of inputs. Compute P2 = initial sequences of non-constant coeffs of all basis elts, Compute each Pijk, where suppose K has three elements, 0 <= i < length of initial sequences of non-constant coeffs of K1, 0 <= j < etc., Qijk is projection computed using ith, jth, and kth reducta of respective elements of K, and Pijk is the result of simplifying Qijk with respect to the side relations that the appropriate initial non-constant coeffs of the elements of K are equal to zero. (Possible precomputation for each Pijk: do a heuristic test (e.g. Groebner basis to check emptiness of complex variety), or cad, to check that real varieties stay nonempty as you take progressively larger sequences of initial non-constant coeffs; if such a variety is empty, then you don't need to continue. It could happen that appropriate tails of initial sequences of elements of K could be thrown out of P2). Set P = P1 un P2 un (all Pijk's). Compute P-invariant decomposition of E^(r-1). (2) Assume now r <= 3; maybe works for general r. (3) Extension phase: On each region in E^(r-1), evaluate the appropriate non-identically zero reducta of elements of K to get a set of algebraic polys; compute its basis. If any element of K is identically zero on this region, determine the appropriate algebraic polynomials whose roots we need to take account of to insure boundary property, compute their basis, merge the two bases. Isolate roots of the final basis to determine the stack over this region. Record K-signature of each element of the stack. Base Phase cad is of r>=1 space; follow chain of induced cad's down to 1-space, contruct cells there. Fill in basisSignature's = primarySignature's of cells. If 1-space cad.localizationFormula # NIL, then discard cells which don't satisfy it. Extension Phase Information to save to pass to adjacency algorithms: E1 to E2: For each 0-cell in E1: isolating intervals (perhaps expanded to be strictly open) and corresponding algebraic basis elements over it; for each element F of integral bivariate basis, a sequence of length m of positive integers, such that F has m real roots over it, and ith element of sequence is section (or element) of overall stack which is ith real root of F. Use this list to modify cell indices of section-section adjacencies produced by adjacency algorithms. E2 to E3: For each 0-cell and 1-cell in E2: isolating intervals (perhaps expanded to be strictly open) and corresponding algebraic basis elements over it; for each element F of integral trivariate basis, a sequence of length m of positive integers, such that F has m real roots over it, and ith element of sequence is section of overall stack which is ith real root of F. Extend cad of dimension-1 space to dimension space, using the largest signed regions (wrt primarySignatures) that can be constructed in the graph for dimension-1 space. Let i = dimension. Assume that in E^(i-1), with primaryPolynomials _ CompleteFactors(inputPolynomials), primarySignatures of cells are set. 1. MaximalSignedRegions[i-1, cad, TRUE]; regions _ ExtractSignedRegions[i-1, cad, TRUE]; sort regions in order of decreasing dimension (for i-1 = 2, put degenerate 0-dimensional regions after nondegenerate). 2. cad.cells _ NIL; Go down sorted list of regions, for each: 2a. currentCells _ ExtendRegionToCells[i, currentRegion, cad]; newAdjacencies _ NIL; If currentRegion is a 0-cell, then as each element of (trivariate) basis is evaluated at sample point, check for identically zero; if so, then add that basis element to identicallyZeroBasisElements field of the 0-cell. If identicallyZeroBasisElements#NIL when all basis elements have been evaluated, i.e. if this is a degenerate 0-cell, then do the extra work required to determine the elements of the stack over this cell (RES sets, etc.), otherwise just isolate the roots of the algebraic basis of evaluated (trivariate integral) basis. 2b. Do this step only if i = 2 or 3. If dimension of currentRegion < i-1, then determine adjacent regions of larger dimension. Sort these into order of increasing dimension. Go down this list, and for each region on it, find all cell-cell adjacencies between currentRegion and this region. Sort these adjacencies into decreasing sum of cell dimensions. For the next such adjacency, newAdjacencies _ AdjacenciesOverAdjacency[i, adjacency, cad]. If newAdjacencies = NIL, i.e. if needed auxiliary E^(i-1) cell-cell adjacencies, or non-NIL sample points, cannot be found, then go to the next cell-cell adjacency between current region and this region. If needed auxiliary adjacencies and/or non-NIL sample points cannot be found for any cell-cell adjacency between current region and this region, give up on building adjacencies in E^i between stacks over current region and this region. Note that there is no need to worry about whether regions have the boundary property; Note the specification that we try to find an adjacency (that we can build adjacencies over) between each pair of adjacent regions; the lower dimensional cell in such an adjacency necessarily belongs to the portion of the lower dimensional region contained in the boundary of the larger dimensional region. 2c. Insert cells of currentCells into cad.cells in lexicographical order. IF newAdjacencies # NIL, then enter its adjacencies into the appropriate cells of cad.cells. 3. If i-space cad.localizationFormula # NIL, then delete all cells of cad.cells which don't satisfy it, and all adjacencies involving those cells . 4. For i = 1, 2 or 3, if no localization, we now have a graph for the cad of E^i in which a maximal signed regions computation will yield (signed) components (in 1 and 2-space, we can have all adjacencies, in 3-space, probably only a proper subset of all adjacencies.) Extend region in dimension-1 space to cells in dimension-space. cad is dimension-space cad. Fill in basisSignatures, and, if desired, (with primaryPolynomials _ CompleteFactors(inputPolynomials)), primarySignatures, of newCells. Also fill in induced adjacencies, and intrastack adjacencies, among newCells. (Let i = dimension). Method: Evaluate polys at base sample point, irreducible basis of algebraic polys, isolate roots, construct extended sample points, eval gsfd of i-variate polynomial at endpoints of isolating interval, or i-variate polynomial itself at easy primitive sector sample point, when we want its sign. Stack: TYPE = REF StackRec; StackRec: TYPE = RECORD [ base: Cell, -- in E^(i-1) baseTruthValue: BOOL, -- used in quantifier elimination elements: CellSeq -- of cells in E^i ]; Return a StackSeq of length one consisting of the stack over cell in E^(i-1). StacksInEi returned in lexicographical order by base RatApproxSamplePoint: PROC [cell: Cells.Cell, ratApproxBound: BR.BigRat] RETURNS [PTS.Point]; Return a rational approximation to cell sample point, each coordinate accurate to within ratApproxBound. Should have the property that always produces the same RatPoint for given RealFieldPoint and ratApproxBound inputs. QEProblem: TYPE = RECORD [ inputFormula: QFF.Formula, localizationFormula: QFF.Formula, equivalentQFFormula: QFF.Formula _ NIL, freeSpaceSignatureTable: SignatureTable _ NIL, cad: Cad _ NIL -- constructed up through k-space, projection data to r-space statistics: QEStatisticsRec, -- to be added later ]; 1. Extract polynomials of formula and localizationFormula; cad _ ProjectionPhase[polynomials, inputVariables, localizationFormula]. 2. Cad.BasePhase[cad]; 3. For i in [2,...,k] do Cad.RegionExtendCadToCad[i, cad]. 4. Cad.MaximalSignedRegions[k, cad, TRUE]; regions _ Cad.ExtractSignedRegions[k, cad, TRUE]; Sort regions into order of decreasing dimension (for k = 3, put degenerate 0-dimensional regions after nondegenerate), since qe for larger dimensional regions should go faster, since they are likely to have lower degree sample points. 5. For each region of regions, using representative cell = cellInEk (which has extended or primitive sample point), do: 5.1 StacksInEk+1 _ Cad.ExtendCellToStacks[k+1, cellInEk, cad]; 5.2 For i in [k+2,...,r] do StacksInEi _ Cad.ExtendStacksToStacks[i, StacksInEiM1, cad]. 5.3. EliminateInnermostQuantifier[StacksInEr, formula]; 5.4. For i decreasing in [k+1,...,r-1] do EliminateInnerQuantifier[i, StacksInEi, StacksInEiM1, formula]; 5.5 If StacksInEk+1.baseTruthValue then insert this signed component into SignatureTable. 6. DisambiguateSignatureTable, extract signatures corresponding to regions in solution set, bundle them up as a SignatureSeq 7. Apply SimplifySignatureSeq; Return SignatureSeqToFormula and the final SignatureTable. Go through StacksInEr determing truth value of formula on each element of each stack, looking at innermost quantifier, and setting baseTruthValue accordingly. Assume baseTruthValue's of StacksInEi already set, and for each stack S in StacksInEiM1, find the stacks in StacksInEi whose bases are the elements of S. Looking at the baseTruthValue's of these stacks in StacksInEi, and the appropriate quantifier in formula, set the baseTruthValue of S. SignatureTable: TYPE = REF SignatureTableRec; SignatureTableBoundsType: TYPE = [1..65534]; SignatureTableRec: TYPE = RECORD [ cad: Cad, -- access to the cad to which the cells of entry regions belong polynomials: POL.PolynomialSeq, -- irreducible (<= r)-variate rational polynomials, all of which occur in the bases of some (possibly 0th) induced cad (and hence are invariant on all cells of the r-space cad), with respect to whose signs the signatures of the entry regions are defined. entries: SEQUENCE lengthPlus1: SignatureTableBoundsType OF SignatureTableEntry ]; SignatureTableEntry: TYPE = REF SignatureTableEntryRec; SignatureTableEntryRec: TYPE = RECORD[ signature: Signature, unambiguous: BOOL, regions: SignedRegionSeq -- each of which has the signature of this TableEntry ]; Assume that initially inTable.polynomials _ inTable.cad.primaryPolynomials. outTable _ copy(inTable). While there is an ambiguous entry in outTable, do for each such ambiguous entry: 1. Select some polynomial P from the basis of some (proper) induced cad, such that P is not an element of outTable.polynomials (use hashing). 2. Augment the secondarySignature's of all cells of all regions of this entry by sign(P). 3. For each region of this entry, form the subgraph it induces, and construct signed components in this subgraph wrt secondarySignature. 4. Collect the cumulative data: if the sign(s) of P on all newly formed components which are contained in the solution set differ from the sign(s) of P on all newly formed components which are external to the solution set, then we have succeeded in disambiguating this entry with P. 5. Delete this entry, and create two new appropriate unambiguous entries, with appropriately augmented signatures. 6. For all unambiguous entries, augment their signatures with "don't care" in the P position, and augment appropriately (i.e. with the correct P sign) the secondarySignature's of all constituent cells of all entry regions. 7. For each ambiguous entry, carry out steps 2,3,4, and see if we have succeeding in disambiguating that entry with P. If so, then carry out step 5 for this entry. If not, then split this entry into up to three or more (each of which may be ambiguous or unambiguous, but at least one of which must be ambiguous if we are here) entries, corresponding to splitting each of the prior entry regions into up to three or more new regions by the sign of P. First determine signatures which do not occur, and use them when helpful. Sort into lexicographical order and combine. Convert to a formula. CadCoodTransform ��/��J��.�.�Ititle��Iauthors�Iabstract��ms�s8�9head��1J�xJ�J�zJ�J��J�J�:J�J�AJ�J�J�J�/J��J��J�1J�J��J��J�%��J�RJ�J��J�J��J��J�<��0J��J�"��J��)J�J�J�I��Iblock�U��O�EO�7O�'��&J��J�!��J��O�J��J�J��J�J�7��;J��@J�J�J�sJ�J��J��J�YJ�J�T��?J�gJ�J�5J�J�5��J��)�*O��O�|O�<��O�S��O�cO�Q�N�8�O��Q�QO��O��O�\��O��O��O�y��N�7�J��J�J��J��J�J�J�AJ�J�J�J�J�:J� J��J�#��J��J�J�.J�J�J��J�J�.J�GJ��AJ�*J��J�BJ��J�PJ�EJ�FJ�� J��J�}J�a��5�5J��J�� @��fP��P�� J�� O�J��7J��J��J��J�1J��6J�HJ��J��J�!J�-�J�1J�� J��4��P�e�P��&J��J��J�xJ��>�>��+��UJ��J��J��J��J��J�� "��qP��[�[P��P��P��J�� J�� J��!�7J��$J�� fP��M�MP��rP��4�4P�� $�� ]P��J�� J�� !J��'J��*��.J��=�LJ��1�1J�� /��P��+P��A��4��P�� P�� :P��w�wP��>P��)��XP��9P��*��)�kP��Z�Z�P��_�}P�� YP�P�� TJ��P�� kJ��P�� J��J��-J��,��"J�� ?�IJ�� J�� '��NJ��J��7��&J��J�� J��5�NJ�� fP��L�LP��P�PP��P��Y�YP��P��P�rP��P��P�� IJ�IJ�,P�� GJ��J��"J��J�J��J�J�M��>J�XJ�LJ�d��N��.O��O��O�\O��O�@O�N��J��"�"J�J��J�J� J�J�3�N��J�8J�� O��O��O��O��O��O��|�|O��O��O��O��O��O��O��O��[�[O��o�o��_��