- Sponsor:
- sigsam
The aim of SNC 2009 is to offer a forum for researchers in symbolic and numeric computation to present their work, interact, exchange ideas and identify important problems in this research area.
SNC 2009 continues a successful tradition of previous highly successful workshops in the area of symbolic and numeric computation:
SNAP 96, held July 15-17, 1996 in Sophia Antipolis, France
SNC 2005, held July 19-21, 2005 in Xi'an, China
SNC 2007, held July 25-27, 2007 in London Ontario, Canada
A warm thank you goes to all those that worked hard to make SNC 2009 happen and in particular the local organizers, the program committee members, the anonymous referees, the invited speakers and the participants. The SNC 2009 Call For Papers solicited submissions in several topics:
Hybrid symbolic-numeric algorithms
Approximate polynomial GCD and factorization
Symbolic-numeric methods for solving polynomial systems
Resultants and structured matrices for symbolic-numeric computation
Differential equations for symbolic-numeric computation
Symbolic-numeric methods for geometric computation
Symbolic-numeric algorithms in algebraic geometry
Symbolic-numeric algorithms for nonlinear optimization
Numeric computation of characteristic sets and Groebner bases
Implementation of symbolic-numeric algorithms
Approximate algebraic algorithms
Applications of symbolic-numeric computation
SNC 2009 is sponsored by the University of Tsukuba (http://www.tsukuba.ac.jp/english/). SNC 2009 is in cooperation with ACM SIGSAM (http://www.sigsam.org/) and we wish to thank the Chair of SIGSAM, Dr. Mark Giesbrecht, for his continuous help and support. SNC 2009 is also in cooperation with JSSAC, the Japan Society for Symbolic and Algebraic Computation (http://www.jssac.org/).
We hope that the current book of proceedings of SNC 2009 will become a useful resource for researchers in Symbolic-Numeric Computation and other related research areas. We also hope that it will become another testament of the liveliness and vibrancy of this research area and a precursor of the future developments that await us ahead.
Proceeding Downloads
Error free transformations of floating point numbers and its applications to constructing efficient error free numerical algorithms
We have proposed error free transformations for floating point numbers[1]-[3]. In the first place, this talk will briely survey this result. Then, the suthor will clarify that this new methodology is very usefull to make efficient error free numerical ...
Preconditioning, randomization, solving linear systems, eigen-solving, and root-finding
We propose novel randomized preprocessing techniques for solving linear systems of equations and eigen-solving with extensions to the solution of polynomial and secular equations. According to our formal study and extensive experiments, the approach ...
Symbolic-numeric problems in the automatic analysis and verification of cyber-physical systems
Cyber-Physical Systems (CPS) are integrations of computation and physical processes. Already now, more or less no new consumer device or industrial machinery does not have some form of integrated computation. Since such systems not only interact with ...
De-Sinc numerical methods
The present talk gives a survey of the DE-Sinc numerical methods (= the Sinc numerical methods, which have been developed by Stenger and his school, incorporated with double-exponential transformations). The DE-Sinc numerical methods have a feature that ...
Rigorous global search using taylor models
A Taylor model of a smooth function f over a sufficiently small domain D is a pair (P,I) where P is the Taylor polynomial of f at a point d in D, and I is an interval such that f differs from P by not more than I over D. As such, they represent a hybrid ...
Exact polynomial factorization by approximate high degree algebraic numbers
For factoring polynomials in two variables with rational coefficients, an algorithm using transcendental evaluation was presented by Hulst and Lenstra. In their algorithm, transcendence measure was computed. However, a constant c is necessary to compute ...
Computing nearest Gcd with certification
A bisection method, based on exclusion and inclusion tests, is used to address the nearest univariate gcd problem formulated as a bivariate real minimization problem of a rational fraction.
The paper presents an algorithm, a first implementation and a ...
Extracting numerical factors of multivariate polynomials from taylor expansions
We present a method to extract factors of multivariate polynomials with complex coefficients in floating point arithmetic. We establish the connection between the reciprocal of a multivariate polynomial and its Taylor expansion. Since the multivariate ...
Experimental evaluation and cross-benchmarking of univariate real solvers
- Michael Hemmer,
- Elias P. Tsigaridas,
- Zafeirakis Zafeirakopoulos,
- Ioannis Z. Emiris,
- Menelaos I. Karavelas,
- Bernard Mourrain
Real solving of univariate polynomials is a fundamental problem with several important applications. This paper is focused on the comparison of black-box implementations of state-of-the-art algorithms for isolating real roots of univariate polynomials ...
An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
Recently quantifier elimination (QE) has been of great interest in many fields of science and engineering. In this paper an effective symbolic-numeric cylindrical algebraic decomposition (SNCAD) algorithm and its variant specially designed for QE are ...
A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions
For a proof of the monotone column permanent (MCP)conjecture for dimension 4 it is sufficient to show that 4 polynomials, which come from the permanents of real matrices, are nonnegative for all real values of the variables, where the degrees and the ...
Curve/surface intersection problem by means of matrix representations
In this paper, we introduce matrix representations of algebraic curves and surfaces for Computer Aided Geometric Design (CAGD). The idea of using matrix representations in CAGD is quite old. The novelty of our contribution is to enable non square ...
Rigorous integration of flows and ODEs using taylor models
Taylor models combine the advantages of numerical methods and algebraic approaches of efficiency, tightly controlled recourses, and the ability to handle very complex problems with the advantages of symbolic approaches, in particularly the ability to be ...
Continued fraction expansion of real roots of polynomial systems
We present a new algorithm for isolating the real roots of a system of multivariate polynomials, given in the monomial basis. It is inspired by existing subdivision methods in the Bernstein basis; it can be seen as generalization of the univariate ...
Application of filter diagonalization method to numerical solution of algebraic equations
By the use of symbolic computation, a problem given by a set of multivariate algebraic relations is often reduced to a univariate algebraic equation which is quite high degree. And, if the roots are required in numbers we generally have to solve the ...
Nearly optimal symbolic-numerical algorithms for structured integer matrices and polynomials
Our unified superfast algorithms for solving Toeplitz, Hankel, Vandermonde, Cauchy, and other structured linear systems of equations with integer coefficients combine Hensel's symbolic lifting and numerical iterative refinement and run in nearly optimal ...
Continuations and monodromy on random riemann surfaces
Our main motivation is to analyze and improve factorization algorithms for bivariate polynomials in C[x,y], which proceed by continuation methods.
We consider a Riemann surface X defined by a polynomial f(x,y) of degree d, whose coefficients are choosen ...
Finding exact minimal polynomial by approximations
We present a new algorithm for reconstructing an exact algebraic number from its approximate value by using an improved parameterized integer relation construction method. Our result is consistent with the existence of error controlling on obtaining an ...
Optimization and NP_R-completeness of certain fewnomials
We give a high precision polynomial-time approximation scheme for the supremum of any honest n-variate (n+2)-nomial with a constant term, allowing real exponents as well as real coefficients. Our complexity bounds count field operations and inequality ...
A method for finding zeros of polynomial equations using a contour integral based eigensolver
In this paper, we present a method for finding zeros of polynomial equations in a given domain. We apply a numerical eigensolver using contour integral for a polynomial eigenvalue problem that is derived from polynomial equations. The Dixon resultant is ...
Computing multivariate approximate GCD based on Barnett's theorem
We present algorithms for multivariate GCD and approximate GCD by modifying Barnett's theorem, which is based on the LU-decomposition of Bézout matrix. Our method is suited for multivariate polynomials with large degrees. Also, we analyze ill-...
Convergence and many-valuedness of hensel seriesnear the expansion point
Hensel series is an expansion of multivariate algebraic function at a singular point, computed from the defining polynomial by the Hensel construction. The Hensel series is well-structured and tractable, hence it seems to be useful in various ...
Approximate factorization of polynomials over Z
We propose three algorithms for approximate factorization of univariate polynomials over Z; the first one uses sums of powers of roots (SPR method), the second one utilizes factor-differentiated polynomials (FD method), and the third one is a robust but ...
Computing clustered close-roots of univariate polynomials
Given a univariate polynomial having well-separated clusters of close roots, we give a method of computing close roots in a cluster simultaneously, without computing other roots. We first determine the position and the size of the cluster, as well as ...
Finding positively invariant sets of a class of nonlinear loops via curve fitting
In this paper, we study positively invariant sets of a class of nonlinear loops and discuss the relation between these sets and the attractors of the loops. For the canonical Hénon map, a numerical method based on curve fitting is proposed to find a ...
Reducing exact computations to obtain exact results based on stabilization techniques
For a certain class of algebraic algorithms, we propose a new method that reduces the number of exact computational steps needed for obtaining exact results. This method is the floating-point interval method using zero rewriting and symbols. Zero ...
Parametrization of ε-rational curves: extended abstract
In this talk we deal with the problem of parametrizing approximately a perturbed rational affine plane curve implicitly given. We present some of our recent results (see [3], [4], [5], [6]) and we describe our on going research in this context. More ...
Index Terms
- Proceedings of the 2009 conference on Symbolic numeric computation