36070731
Decomposing Polynomial Systems into Simple Systems
A simple system is a pair of multivariate polynomial sets (one set for equations and the other for inequations) ordered in triangular form, in which every polynomial is squarefree and has non-vanishing leading coefficient with respect to its leading variable. This paper presents a method that decomposes any pair of polynomial sets into finitely many simple systems with an associated zero decomposition. The method employs top-down elimination with splitting and the formation of subresultant regular subchains as basic operation.
46198564
Reasoning about Surfaces Using Differential Zero and Ideal Decomposition
This paper presents methods for zero and ideal decomposition of partial differential polynomial systems and the application of these methods and their implementations to deal with problems from the local theory of surfaces. We show how to prove known geometric theorems and to derive unknown relations automatically. In particular, an algebraic relation between the first and the second fundamental coefficients in a very compact form has been derived, which is more general and has smaller degree than a relation discovered previously by Z. Li. Moreover, we provide symmetric expressions for Li's relation and clarify his statement. Some examples of theorem proving and computational difficulties encountered in our experiments are also discussed.
35725775
A simple method for implicitizing rational curves and surfaces
Abstract This paper presents a simple method for converting rational parametric equations of curves and surfaces into implicit equations. The method proceeds via writing out the implicit polynomial F of estimated degree with indeterminate coefficients u i , substituting the rational expressions for the given parametric curve or surface into F to yield a rational expression g / h in the parameter s (or s and t ), equating the coefficients of g in terms of s (and t ) to 0 to generate a sparse, partially triangular system of linear equations in u i with constant coefficients, and finally solving the linear system for u i . If a nontrivial solution is found, then an implicit polynomial is obtained; otherwise, one repeats the same process, increasing the degree of F . Our experiments show that this simple method is efficient. It performs particularly well in the presence of base points and may detect the dependency of parameters incidentally.
39506333
GEOTHER: A Geometry Theorem Prover
20258295
Automated Generation of Diagrams with Maple and Java
This note shows how to draw diagrams automatically from the predicate specification of a given set of geometric relations among a set of points in the plane. It is done first in Maple by translating the geometric relations into polynomial equations, decomposing the obtained system of polynomials into irreducible representative triangular sets, and finding an adequate numerical solution from each triangular set. A Java class coding the solution and the polynomials in each triangular set is generated, compiled, and then executed with the main Java programs to draw a diagram. The whole process combining symbolic elimination in Maple with numerical computation, graphic drawing, and letter labeling in Java is fully automatic. The drawn diagrams may be animated and fine-tuned by mouse click and dragging and saved as PostScript files. We present the drawing method, discuss some techniques of implementation, and give several sample diagrams drawn by our program.
10779017
On Wu's Method for Proving Constructive Geometric Theorems
In 1977 Wu Wen-tsiin discovered an efficient method for mechanical theorem proving. This method has been applied to prove and discover theorems in various kinds of geometries. Based on an extension of one of Wu's algorithmic procedures, the author implemented a prover CPS for proving so-called constructive geometric theorems, as well as a general theorem prover PS. Using this prover we proved more than one hundred non-trivial theorems and discovered also a number of interesting ones. This paper is a summarization of our early work, as a abbreviation of the chapter 2 from my Chinese doctoral dissertation.
20528314
Anticipation Model for Sequential Learning of Complex Sequences
One of the fundamental aspects of human intelligence is the ability to process temporal information (Lashley, 1951). Learning and reproducing temporal sequences are closely associated with our ability to perceive and generate body movements, speech and language, music, etc. A considerable body of neural network literature is devoted to temporal pattern generation (see Wang, 2001, for a recent review). These models generally treat a temporal pattern as a sequence of discrete patterns, called a temporal sequence. Most of the models are based on either multilayer perceptrons with backpropagation training or the Hopfield model of associative recall. The basic idea for the former class of models is to view a temporal sequence as a set of associations between consecutive components, and learn these associations as input-output transformations (Jordan, 1986; Elman, 1990; Mozer, 1993). To deal with temporal dependencies beyond consecutive components, part of the input layer is used to keep a trace of history, behaving as short-term memory (STM). Similarly, for temporal recall based on the Hopfield associative memory, a temporal sequence is viewed as associations between consecutive components. These associations are stored in extended versions of the Hopfield model that includes some time delays (Sompolinsky & Kanter, 1986; Buhmann & Schulten, 1987; Heskes & Gielen, 1992). To deal with longer temporal dependencies, high-order networks have been proposed (Guyon et al., 1988).
980946
Image and Texture Segmentation Using Local Spectral Histograms
We present a method for segmenting images consisting of texture and nontexture regions based on local spectral histograms. Defined as a vector consisting of marginal distributions of chosen filter responses, local spectral histograms provide a feature statistic for both types of regions. Using local spectral histograms of homogeneous regions, we decompose the segmentation process into three stages. The first is the initial classification stage, where probability models for homogeneous texture and nontexture regions are derived and an initial segmentation result is obtained by classifying local windows. In the second stage, we give an algorithm that iteratively updates the segmentation using the derived probability models. The third is the boundary localization stage, where region boundaries are localized by building refined probability models that are sensitive to spatial patterns in segmented regions. We present segmentation results on texture as well as nontexture images. Our comparison with other methods shows that the proposed method produces more accurate segmentation results
15831894
Perceptual organization based on temporal dynamics
This paper presents a computational model for perceptual organization. A figure-ground segregation network is proposed based on a novel boundary pair representation. The system solves the figure-ground segregation problem through temporal evolution. Gestalt-like grouping rules are incorporated by modulating connections, which determines the temporal behavior and thus the perception of the system. The results are then fed to a surface completion module based on local diffusion. Different perceptual phenomena, such as modal and a modal completion, virtual contours, grouping and shape decomposition are explained by the model with a fixed set of parameters. Computationally, the system eliminates combinatorial optimization, which is common to many existing computational approaches. It also accounts for more examples that are consistent with psychological experiments. In addition, the boundary-pair representation is consistent with well-known on- and off-center cell responses and thus biologically more plausible.
748050
Oriented statistical nonlinear smoothing filter
This paper presents a nonlinear smoothing method which is based on an orientation-sensitive probability measure. By incorporating geometrical constraints through the coupling structure, we obtain a robust nonlinear smoothing algorithm. Even when noise is substantial the proposed smoothing algorithm can still preserve salient boundaries. Compared with anisotropic diffusive approaches, the proposed nonlinear algorithm not only performs better in preserving boundaries but also has a non-uniform stable state, whereby reliable results are available within a fixed number of iterations independent of images. A system using the proposed method and LEGION network has been developed and applied in noisy image segmentation and hydrographic feature extraction from digital ortho-photo quadrangles. Experimental results using synthetic and real images are provided.
1420299
Server-Side Parallel Data Reduction and Analysis
Geoscience analysis is currently limited by cumbersome access and manipulation of large datasets from remote sources. Due to their data-heavy and compute-light nature, these analysis workloads represent a class of applications unsuited to a computational grid optimized for compute-intensive applications. We present the Script Workflow Analysis for MultiProcessing (SWAMP) system, which relocates data-intensive workflows from scientists' workstations to the hosting datacenters in order to reduce data transfer and exploit locality. Our colocation of computation and data leverages the typically reductive characteristics of these workflows, allowing SWAMP to complete workflows in a fraction of the time and with much less data transfer. We describe SWAMP's implementation and interface, which is designed to leverage scientists' existing script-based workflows. Tests with a production geoscience workflow show drastic improvements not only in overall execution time, but in computation time as well. SWAMP's workflow analysis capability allows it to detect dependencies, optimize I/O, and dynamically parallelize execution. Benchmarks quantify the drastic reduction in transfer time, computation time, and end-to-end execution time.