Skip to main content

2008 | Buch

Computer Mathematics

8th Asian Symposium, ASCM 2007, Singapore, December 15-17, 2007. Revised and Invited Papers

insite
SUCHEN

Über dieses Buch

This book constitutes thoroughly refereed post-conference proceedings of the 8th Asian Symposium on Computer Mathematics, ASCM 2007, held in Singapore in December 2007. The 22 revised full papers and 5 revised poster papers presented together with 3 invited lectures were carefully selected during two rounds of reviewing and improvement from 65 submissions. The papers are organized in topical sections on algorithms and implementations, numerical methods and applications, cryptology, and computational logic.

Inhaltsverzeichnis

Frontmatter

Algorithms and Implementations

Computing the Minkowski Value of the Exponential Function over a Complex Disk
Abstract
Basic concepts, results, and applications of the Minkowski geometric algebra of complex sets are briefly reviewed, and preliminary ideas on its extension to evaluating transcendental functions of complex sets are discussed. Specifically, the Minkowski value of the exponential function over a disk in the complex plane is considered, as the limit of partial–sum sets defined by the monomial or Horner evaluation schemes.
Hyeong In Choi, Rida T. Farouki, Chang Yong Han, Hwan Pyo Moon
Unconstrained Parametric Minimization of a Polynomial: Approximate and Exact
Abstract
We consider a monic polynomial of even degree with symbolic coefficients. We give a method for obtaining an expression in the coefficients (regarded as parameters) that is a lower bound on the value of the polynomial, or in other words a lower bound on the minimum of the polynomial. The main advantage of accepting a bound on the minimum, in contrast to an expression for the exact minimum, is that the algebraic form of the result can be kept relatively simple. Any exact result for a minimum will necessarily require parametric representations of algebraic numbers, whereas the bounds given here are much simpler. In principle, the method given here could be used to find the exact minimum, but only for low degree polynomials is this feasible; we illustrate this for a quartic polynomial. As an application, we compute rectifying transformations for integrals of trigonometric functions. The transformations require the construction of polynomials that are positive definite.
S. Liang, D. J. Jeffrey
The Nearest Real Polynomial with a Real Multiple Zero in a Given Real Interval
Abstract
Given f ∈ ℝ[x] and a closed real interval I, we provide a rigorous method for finding a nearest polynomial with a real multiple zero in I, that is, \(\tilde{f}\in\mathbb{R}[x]\) such that \(\tilde{f}\) has a multiple zero in I and \(\|f - \tilde{f}\|_\infty\), the infinity norm of the vector of coefficients of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-87827-8_3/MediaObjects/978-3-540-87827-8_3_IEq4_HTML.png , is minimal. First, we prove that if a nearest polynomial https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-87827-8_3/MediaObjects/978-3-540-87827-8_3_IEq5_HTML.png exists, there is a nearest polynomial \(\tilde{g}\in\mathbb{R}[x]\) such that the absolute value of every coefficient of \(f-\tilde{g}\) is \(\|f - \tilde{f}\|_\infty\) with at most one exceptional coefficient. Using this property, we construct h ∈ ℝ[x] such that a zero of h is a real multiple zero α ∈ I of \(\tilde{g}\). Furthermore, we give a rational function whose value at α is \(\|f - \tilde{f}\|_\infty\).
Hiroshi Sekigawa
Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping
Abstract
Let https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-87827-8_4/MediaObjects/978-3-540-87827-8_4_IEq1_HTML.png be a polynomial of degree D. Computing the set of generalized critical values of the mapping https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-87827-8_4/MediaObjects/978-3-540-87827-8_4_IEq2_HTML.png (i.e. https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-87827-8_4/MediaObjects/978-3-540-87827-8_4_IEq3_HTML.png ) is an important step in algorithms computing sampling points in semi-algebraic sets defined by a single inequality.
A previous algorithm allows us to compute the set of generalized critical values of \(\widetilde{f}\). This one is based on the computation of the critical locus of a projection on a plane P. This plane P must be chosen such that some global properness properties of some projections are satisfied. These properties, which are generically satisfied, are difficult to check in practice. Moreover, choosing randomly the plane P induces a growth of the coefficients appearing in the computations.
We provide here a new certified algorithm computing the set of generalized critical values of \(\widetilde{f}\). This one is still based on the computation of the critical locus on a plane P. The certification process consists here in checking that this critical locus has dimension 1 (which is easy to check in practice), without any assumption of global properness. Moreover, this allows us to limit the growth of coefficients appearing in the computations by choosing a plane P defined by sparse equations. Additionally, we prove that the degree of this critical curve is bounded by \((D-1)^{n-1}-\mathfrak{d}\) where \(\mathfrak{d}\) is the sum of the degrees of the positive dimensional components of the ideal \(\langle \frac{\partial f}{\partial X_1}, \ldots,\frac{\partial f}{\partial X_n}\rangle\).
We also provide complexity estimates on the number of arithmetic operations performed by a probabilistic version of our algorithm.
Practical experiments at the end of the paper show the relevance and the importance of these results which improve significantly in practice previous contributions.
Mohab Safey El Din
Which Symmetric Homogeneous Polynomials Can Be Proved Positive Semi-definite by Difference Substitution Method?
Abstract
Recently a method based on substitution of difference of variables has been developed by Yang [12] for verifying the positive semi-definiteness of homogeneous polynomials. In this paper, we investigate the structure of the cone formed by all symmetric homogeneous polynomials whose positive semi-definiteness can proven by difference substitution method.
Liangyu Chen, Zhenbing Zeng
Basis-Independent Polynomial Division Algorithm Applied to Division in Lagrange and Bernstein Basis
Abstract
Division algorithms for univariate polynomials represented with respect to Lagrange and Bernstein basis are developed. These algorithms are obtained by abstracting from the classical polynomial division algorithm for polynomials represented with respect to the usual power basis. It is shown that these algorithms are quadratic in the degrees of their inputs, as in the power basis case.
Manfred Minimair
Computing the Greatest Common Divisor of Polynomials Using the Comrade Matrix
Abstract
The comrade matrix of a polynomial is an analogue of the companion matrix when the matrix is expressed in terms of a general basis such that the basis is a set of orthogonal polynomials satisfying the three-term recurrence relation. We present the algorithms for computing the comrade matrix, and the coefficient matrix of the corresponding linear systems derived from the recurrence relation. The computing times of these algorithms are analyzed. The computing time bounds, which dominate these times, are obtained as functions of the degree and length of the integers that represent the rational number coefficients of the input polynomials. The ultimate aim is to apply these computing time bounds in the analysis of the performance of the generalized polynomial greatest common divisor algorithms.
Nor’aini Aris, Shamsatun Nahar Ahmad
Efficient Algorithms for Computing Nœther Normalization
Abstract
In this paper, we provide first a new algorithm for testing whether a monomial ideal is in Nœther position or not, without using its dimension, within a complexity which is quadratic in input size. Using this algorithm, we provide also a new algorithm to put an ideal in this position within an incremental (one variable after the other) random linear change of the last variables without using its dimension. We describe a modular (probabilistic) version of these algorithms for any ideal using the modular method used in [2] with some modifications. These algorithms have been implemented in the distributed library noether.lib [17] of Singular, and we evaluate their performance via some examples.
Amir Hashemi
Stability of GPBiCG_AR Method Based on Minimization of Associate Residual
Abstract
GPBi-CG method is an attractive iterative method for the solution of a linear system of equations with nonsymmetric coefficient matrix. However, the popularity of GPBi-CG method has diminished over time except for the minority. In this paper, we consider a new algorithm based on minimization of the associate residual of 2-norm in place of reconstruction of the algorithm. We refer to a method with new algorithm as GPBiCG with Associate Residual (abbreviated as GPBiCG_AR) method. Moreover we will introduce preconditioned GPBiCG_AR (abbreviated as P_GPBiCG_AR). Then, we will support that GPBiCG_AR and P_GPBiCG_AR methods yield safety convergence through numerical experiments.
Moe Thuthu, Seiji Fujino
Evaluation of a Java Computer Algebra System
Abstract
This paper evaluates the suitability of Java as an implementation language for the foundations of a computer algebra library. The design of basic arithmetic and multivariate polynomial interfaces and classes have been presented in [1]. The library is type-safe due to its design with Java’s generic type parameters and thread-safe using Java’s concurrent programming facilities. We evaluate some key points of our library and differences to other computer algebra systems.
Heinz Kredel
A New Property of Hamming Graphs and Mesh of d-ary Trees
Abstract
In this article we characterize two well-known graphs used in many applications, particularly in network applications: Hamming graphs and meshes of d-ary trees MT(d,1). More precisely, we show that they are so-called \(\mathbb{G}\)-graphs. \(\mathbb{G}\)-graphs are a new type of graphs constructed from a group. They have nice algebraic proprieties and can be regular or semi-regular.
Alain Bretto, Cerasela Jaulin, Luc Gillibert, Bernard Laget

Numerical Methods and Applications

An Interpolation Method That Minimizes an Energy Integral of Fractional Order
Abstract
An interpolation method that minimizes an energy integral will be discussed. To be precise, given N + 1 points (x 0,c 0), (x 1,c 1),..., (x N ,c N ) with 0 = x 0 < x 1 < ⋯ < x N  = 1 and c 0 = c N  = 0, we shall be interested in finding a sufficiently smooth function u on [0,1] that passes through these N + 1 points and minimizes the energy integral \(E_\alpha(u) := \int_0^1 |u^{(\alpha)}(x)|^2 dx\), where u (α) denotes the fractional derivative of u of order α. As suggested in [1], a Fourier series approach as well as functional analysis arguments can be used to show that such a function exists and is unique. An iterative procedure to obtain the function will be presented and some examples will be given here.
H. Gunawan, F. Pranolo, E. Rusyaman
Solving Biomechanical Model Using Third-Order Runge-Kutta Methods
Abstract
A certain biomechanical model involves ordinary differential equations. This research focuses on solving a biomechanical model of a cyclist coasting downhill. The objective of this study is to establish the velocity of the model, using two numerical methods, i.e., the third-order Runge-Kutta methods. The two methods are the existing classical Runge-Kutta and a modified Runge-Kutta method formed by Wazwaz. The numerical results obtained from these two methods are compared with the exact solution and the relative errors are produced.
R. R. Ahmad, A. S. Rambely, L. H. Lim
An Efficient Fourth Order Implicit Runge-Kutta Algorithm for Second Order Systems
Abstract
We will present an algorithmic approach to the implementation of a fourth order two stage implicit Runge-Kutta method to solve periodic second order initial value problems. The systems involved will be solved using some type of factorization that usually involves both complex and real arithmetic. We will consider the real type case which will be efficient and leads to a system that is one fourth the size of similar systems using normal implicit Runge-Kutta method. We will present some numerical examples to show the efficiency of the method.
Basem S. Attili
Laplace Equation Inside a Cylinder: Computational Analysis and Asymptotic Behavior of the Solution
Abstract
The Laplacian in the cylindrical coordinate space has been considered to approximate the solution of a conservative field within a restricted domain.
$$ {{\partial^{2}\psi} \over {\partial\rho^2}} + {{1\delta\psi} \over {\rho\partial\rho}} + {{1} \over {\rho^2}}{ {\partial^{2}\psi} \over {\partial\phi^2}} +{{\partial^{2}\psi} \over {\partial{z}^2} } =0 $$
Solutions of the Laplacian are represented by expansion in series of the appropriate orthonormal functions. By using asymptotic relations of Bessel Series and Fourier Bessel series, we establish some criteria for the solution to properly reflect the nature of the conservative field.
Suvra Sarkar, Sougata Patra
A Method and Its Implementation for Constructing Bäcklund Transformations to Nonlinear Evolution Equations
Abstract
An algorithmic method to construct a kind of auto Bäcklund transformations (BTs) is proposed. A Maple package AutoBT, which can entirely automatically generate auto BT is presented. AutoBT has been effectively applied to many nonlinear evolution equations with physical significance. Not only are previously known BT recovered but also in some cases new and more general form of BT are obtained.
Zhibin Li, Yinping Liu, Haifeng Qian
On the Invariant Properties of Hyperbolic Bivariate Third-Order Linear Partial Differential Operators
Abstract
Bivariate, hyperbolic third-order linear partial differential operators under the gauge transformations Lg(x,y)− 1 ∘ L ∘ g(x,y) are considered. The existence of a factorization, the existence of a factorization that extends a given factorization of the symbol of the operator are expressed in terms of the invariants of some known generating set of invariants. The operation of taking the formal adjoint can be also defined for equivalent classes of LPDOs, and explicit formulae defining this operation in the space invariants were obtained.
Ekaterina Shemyakova, Franz Winkler
Symbolic Solution to Magnetohydrodynamic Hiemenz Flow in Porous Media
Abstract
A system of nonlinear ordinary differential equations governing the boundary layers of magnetohydrodynamic (MHD) Hiemenz flow in porous media is solved using a simple and efficient analytical technique of Adomian decomposition method (ADM) and Padé approximant through the computer algebra package system Maple. Several symbolic features of the Maple system are utilized to develop specific routines that compute the approximate analytical solutions of the stream, velocity and temperature functions for some exemplary prescribed parameters. Comparative study shows the well agreement of the present symbolic results with the existing numerical results.
Seripah Awang Kechil, Ishak Hashim
Local Similarity Solutions for Laminar Boundary Layer Flow along a Moving Cylinder in a Parallel Stream
Abstract
The present paper deals with a numerical method to analyze the axisymmetric boundary layer flow of a viscous and incompressible fluid along a static or moving cylinder, using local similarity approximation. Both parallel and reverse moving boundary to the free stream are considered. Local similarity solutions are obtained to show the effects of the velocity ratio parameter and the curvature parameter on the surface shear stress. The numerical results are comparable very well with the existing results available in the literature for some particular cases of the present problem. Moreover, the results indicate that dual solutions exist when the cylinder and the free stream move in opposite directions.
Anuar Ishak, Roslinda Nazar, Ioan Pop

Elimination: Triangular Forms, Resultants, Equation Solving

An Algorithm for Transforming Regular Chain into Normal Chain
Abstract
We present an improved algorithm to compute the normal chain from a given regular chain such that their saturation ideals are the same. Our algorithm is based on solving a system of linear equations and the original method computes the resultants of multivariate polynomials. From the experiments, for the random polynomials, our algorithm is much more efficient than the original one.
Banghe Li, Dingkang Wang
A Modified Van der Waerden Algorithm to Decompose Algebraic Varieties and Zero-Dimensional Radical Ideals
Abstract
In this paper, we introduce a modified Van der Waerden algorithm to decompose a variety into the union of irreducible varieties. We give an effective representation for irreducible varieties obtained by the algorithm, which allows us to obtain an irredundant decomposition easily. We show that in the zero dimensional case, the polynomial systems for the irreducible varieties obtained in the Van der Waerden algorithm generate prime ideals. As a consequence, we have an algorithm to decompose the radical ideal generated by a finite set of polynomials as the intersection of prime ideals and the degree of the polynomials in the computation is bounded by O(d n ) where d is the degree of the input polynomials and n is the number of variables.
Jia Li, Xiao-Shan Gao
Regular Decompositions
Abstract
We introduce the notion of regular decomposition of an ideal and present a first algorithm to compute it. Designed to avoid generic perturbations and eliminations of variables, our algorithm seems to have a good behaviour with respect to the sparsity of the input system. Beside, the properties of the regular decompositions allow us to deduce new algorithms for the computation of the radical and the weak equidimensional decomposition of an ideal. A first implementation shows promising results.
Guillaume Moroz
Floating-Point Gröbner Basis Computation with Ill-conditionedness Estimation
Abstract
Computation of Gröbner bases of polynomial systems with coefficients of floating-point numbers has been a serious problem in computer algebra for many years; the computation often becomes very unstable and people did not know how to remove the instability. Recently, the present authors clarified the origin of instability and presented a method to remove the instability. Unfortunately, the method is very time-consuming and not practical. In this paper, we first investigate the instability much more deeply than in the previous paper, then we give a theoretical analysis of the term cancellation which causes loss of accuracy in various cases. On the basis of this analysis, we propose a practical method for computing Gröbner bases with coefficients of floating-point numbers. The method utilizes multiple precision floating-point numbers, and it removes the drawbacks of the previous method almost completely. Furthermore, we present a practical method of estimating the ill-conditionedness of the input system.
Tateaki Sasaki, Fujio Kako
The Maximality of the Dixon Matrix on Corner-Cut Monomial Supports
Abstract
It has been established that the bivariate Dixon matrix persists to be the exact resultant when there are at most two exposed points at each corner of a corner-cut support; but it becomes singular when there are four or more exposed points at any of the corners. For the remaining case of three or fewer exposed points at each of the corners, it is observed that the Dixon matrix is maximal but its determinant is a multiple of the resultant with a priori known bracket powers as the extraneous factors. The maximality of the Dixon matrix for the three-or-fewer exposed points case has been established mechanically for the special situation in which the excess degree is unity when there are three exposed points at a corner. This paper presents a greatly simplified mechanical proof so that its validity can be easily verified.
Eng-Wee Chionh
Properties of Ascending Chains for Partial Difference Polynomial Systems
Abstract
A characteristic set theory for partial difference polynomial systems is proposed. We introduce the concept of coherent and regular ascending chains and prove that a partial difference ascending chain is the characteristic set of its saturation ideal if and only if it is coherent and regular. This gives a method to decide whether a polynomial belongs to the saturation ideal of an ascending chain. We introduce the concept of strongly irreducible ascending chains and prove that a partial difference ascending chain is the characteristic set of a reflexive prime ideal if and only if it is strongly irreducible. This gives a simple and precise representation for reflexive prime ideals.
Gui-Lin Zhang, Xiao-Shan Gao

Cryptology

Some Mathematical Problems in Cryptanalysis
Abstract
The talk will recall some basic mathematical problems on analyzing both symmetric and asymmetric ciphers. A special focus will be on the advances in asymmetric ciphers based on the research of some fundamentally hard mathematical problems. Some fundamental statistical problems and cryptanalysis techniques for symmetric cipher will be reviewed as well.
Xiaoyun Wang
A Reduction Attack on Algebraic Surface Public-Key Cryptosystems
Abstract
An algebraic surface public-key cryptosystem was developed by Akiyama and Goto. Its security is based on a decision randomizing polynomial problem which is related to a problem of finding sections on fibered algebraic surfaces which can be reduced to solving a multivariate equation system known to be NP-complete. In the case that the defining equation of a surface used for public-key is in a certain form, Uchiyama and Tokunaga succeeded in attacking in the sense of getting plain texts from corresponding ciphertexts using reductions efficiently without solving section finding problem. In this paper, two algorithms applicable to all cases are suggested. One is the generalization of Uchiyama-Tokunaga’s attack from polynomial ring over https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-87827-8_27/MediaObjects/978-3-540-87827-8_27_IEq1_HTML.png to polynomial ring over rational function field, and the other takes advantages of Gröbner base techniques so as to deal with in the polynomial ring over https://static-content.springer.com/image/chp%3A10.1007%2F978-3-540-87827-8_27/MediaObjects/978-3-540-87827-8_27_IEq2_HTML.png .
Maki Iwami

Computational Logic

The Four Colour Theorem: Engineering of a Formal Proof
Abstract
The 150 year old Four Colour Theorem is the first famous result with a proof that requires large computer calculations. Such proofs are still controversial: It is thought that computer programs cannot be reviewed with mathematical rigor.
To overturn this belief, we have created a fully computer-checked proof of the Four Colour Theorem. Using the Coq proof assistant, we wrote an extended program that specifies both the calculations and their mathematical justification. Only the interface of the program – the statement of the theorem – needs to be reviewed. The rest (99.8%) is self-checking: Coq verifies that it strictly follows the rules of logic. Thus, our proof is more rigorous than a traditional one.
Our effort turned out to be more than just an exercise in verification; having to definine rigorously all key concepts provided new mathematical insight into the concept of planarity. Planarity has topological and combinatorial characterizations, which are often confused in arguments that are both pictorially appealing and logically incomplete. The rigor of our computer proof imposed a strict separation between the two.
We developed a purely combinatorial theory of planarity based on a symmetrical presentation of hypermaps, which greatly simplified the proof. The theory supplies an elegant analogue of the Jordan Curve property, which allowed us to prove the Theorem under minimal topological assumptions, without appealing to Jordan Curve theorem.
Georges Gonthier
On the Computation of Elimination Ideals of Boolean Polynomial Rings
Abstract
In order to compute an eliminate portion of a given polynomial ideal by a Gröbner basis computation, we usually need to compute a Gröbner basis of the whole ideal with respect to some proper term order. In a boolean polynomial ring, we show that we can compute an eliminate portion by computing Gröbner bases in the boolean polynomial ring with the same coefficient ring that has the only variables which we want to eliminate. We also check the efficiency of our method through our implementation.
Yosuke Sato, Akira Nagai, Shutaro Inoue
Computer Search for Large Sets of Idempotent Quasigroups
Abstract
A collection of n − 2 idempotent quasigroups of order n is called a large set if any two of them are disjoint, denoted by LIQ(n). While the existence of ordinary LIQ(n) has been extensively studied, the spectrums of large sets of idempotent quasigroups with various identities remain open, for example, large set of Steiner pentagon quasigroups of order 11 which is denoted by LSPQ(11). This paper describes some computer searching efforts seeking to solve such problems. A series of results are obtained, including the non-existence of LSPQ(11).
Feifei Ma, Jian Zhang
Backmatter
Metadaten
Titel
Computer Mathematics
herausgegeben von
Deepak Kapur
Copyright-Jahr
2008
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-87827-8
Print ISBN
978-3-540-87826-1
DOI
https://doi.org/10.1007/978-3-540-87827-8

Premium Partner