共查询到20条相似文献,搜索用时 78 毫秒
1.
《Journal of Symbolic Computation》1997,24(5):591-622
A new algorithm for the symbolic computation of polynomial conserved densities for systems of nonlinear evolution equations is presented. The algorithm is implemented inMathematica. The programcondens.mautomatically carries out the lengthy symbolic computations for the construction of conserved densities. The code is tested on several well-known partial differential equations from soliton theory. For systems with parameters,condens.mcan be used to determine the conditions on these parameters so that a sequence of conserved densities might exist. The existence of a large number of conservation laws is a predictor for integrability of the system. 相似文献
2.
The computation of coprime fractions for proper rational matrices and the solving of the minimal design problem are important in the design of multivariable systems by using polynomial fractional terms. A recursive algorithm, which fully exploits the shift-invariant property of the generalized resultants, is developed to carry out these computations. A method for solving the Diophantine equation that is based on this algorithm is outlined. This results in a significant reduction in computation as compared to the standard methods involving solution of linear algebraic equations. Some comparisons to existing methods show that the present algorithm is computationally more attractive with regard to efficiency and accuracy 相似文献
3.
Systems of polynomial equations with coefficients over a field K can be used to concisely model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over the algebraic closure of the field K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert’s Nullstellensatz certificates for polynomial systems arising in combinatorics, and based on fast large-scale linear-algebra computations over K. We also describe several mathematical ideas for optimizing our algorithm, such as using alternative forms of the Nullstellensatz for computation, adding carefully constructed polynomials to our system, branching and exploiting symmetry. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph instances with almost two thousand nodes and tens of thousands of edges. 相似文献
4.
《CVGIP: Image Understanding》1992,55(2):109-118
When a three dimensional object is known to be lying on a planar surface, its pose is restricted from six to three degrees of freedom. Computer vision algorithms can exploit the few stable poses of modeled objects to simplify scene interpretation and more accurately determine object location. This paper presents necessary and sufficient conditions for the pose of a piecewise smooth curved three-dimensional object to be stable. For objects whose surfaces are represented by implicit algebraic equations, these conditions can be expressed as systems of polynomial equations that are readily solved by homotopy continuation. Examples from the implemented algorithm are presented. 相似文献
5.
Cheon-Hyeon Park Gershon Elber Ku-Jin Kim Gye-Young Kim Joon-Kyung Seong 《Computer aided design》2011,43(11):1360-1369
This paper deals with a problem of finding valid solutions to systems of polynomial constraints. Although there have been several quite successful algorithms based on domain subdivision to resolve this problem, some major issues are still demanding further research. Prime obstacles in developing an efficient subdivision-based polynomial constraint solver are the exhaustive, although hierarchical, search of the zero-set in the parameter domain, which is computationally demanding, and their scalability in terms of the number of variables. In this paper, we present a hybrid parallel algorithm for solving systems of multivariate constraints by exploiting both the CPU and the GPU multicore architectures. We dedicate the CPU for the traversal of the subdivision tree and the GPU for the multivariate polynomial subdivision. By decomposing the constraint solving technique into two different components, hierarchy traversal and polynomial subdivision, each of which is more suitable to CPUs and GPUs, respectively, our solver can fully exploit the availability of hybrid, multicore architectures of CPUs and GPUs. Furthermore, our GPU-based subdivision method takes advantage of the inherent parallelism in the multivariate polynomial subdivision. We demonstrate the efficacy and scalability of the proposed parallel solver through several examples in geometric applications, including Hausdorff distance queries, contact point computations, surface–surface intersections, ray trap constructions, and bisector surface computations. In our experiments, the proposed parallel method achieves up to two orders of magnitude improvement in performance compared to the state-of-the-art subdivision-based CPU solver. 相似文献
6.
I. A. Fotiou P. Rostalski P. A. Parrilo M. Morari 《International journal of control》2013,86(11):1340-1358
We present two algebraic methods to solve the parametric optimization problem that arises in non-linear model predictive control. We consider constrained discrete-time polynomial systems and the corresponding constrained finite-time optimal control problem. The first method is based on cylindrical algebraic decomposition. The second uses Gröbner bases and the eigenvalue method for solving systems of polynomial equations. Both methods aim at moving most of the computational burden associated with the optimization problem off-line, by pre-computing certain algebraic objects. Then, an on-line algorithm uses this pre-computed information to obtain the solution of the original optimization problem in real time fast and efficiently. Introductory material is provided as appropriate and the algorithms are accompanied by illustrative examples. 相似文献
7.
Keqin Li 《The Journal of supercomputing》2010,54(3):271-297
We present fast and highly scalable parallel computations for a number of important and fundamental matrix problems on distributed
memory systems (DMS). These problems include matrix multiplication, matrix chain product, and computing the powers, the inverse,
the characteristic polynomial, the determinant, the rank, the Krylov matrix, and an LU- and a QR-factorization of a matrix,
and solving linear systems of equations. Our highly scalable parallel computations for these problems are based on a highly
scalable implementation of the fastest sequential matrix multiplication algorithm on DMS. We show that compared with the best
known parallel time complexities on parallel random access machines (PRAM), the most powerful but unrealistic shared memory
model of parallel computing, our parallel matrix computations achieve the same speeds on distributed memory parallel computers
(DMPC), and have an extra polylog factor in the time complexities on DMS with hypercubic networks. Furthermore, our parallel
matrix computations are fully scalable on DMPC and highly scalable over a wide range of system size on DMS with hypercubic
networks. Such fast (in terms of parallel time complexity) and highly scalable (in terms of our definition of scalability)
parallel matrix computations were rarely seen before on any distributed memory systems. 相似文献
8.
Fast interference detection between geometric models 总被引:8,自引:0,他引:8
We present efficient algorithms for interference detection between geometric models described by linear or curved boundaries
and undergoing rigid motion. The set of models include surfaces described by rational spline patches or piecewise algebraic
functions. In contrast to previous approaches, we first describe an efficient algorithm for interference detection between
convex polytopes using coherence and local features. Then an extension using hierarchical representation to concave polytopes
is presented. We apply these algorithms along with properties of input models, local and global algebraic methods for solving
polynomial equations, and the geometric formulation of the problem to devise efficient algorithms for convex and nonconvex
curved objects. Finally, a scheduling scheme to reduce the frequency of interference detection in large environments is described.
These algorithms have been successfully implemented and we discuss their performance in various environments. 相似文献
9.
10.
Y. SHAMASH 《International journal of systems science》2013,44(7):645-652
There are many algorithms for deriving a state variable model for a system defined by a matrix transfer function. It is shown how these algorithms may be applied to the derivation of state variable models for systems defined by linear constant differential equations. without the use of polynomial computations. 相似文献
11.
In this paper, an implementation of the FGLM algorithm that transforms Gröbner bases from one ordering to another is presented. Some additional optimizations that considerably expedite computations are considered. It is shown that this algorithm can be used for finding roots of polynomial systems represented in the involutive form. 相似文献
12.
A. B. Sizonenko 《Automatic Control and Computer Sciences》2013,47(1):15-21
Methods for vector and multiple logical computations are described. An algorithm is presented that allows for parallel computations of the values of the conjunctive terms of generalized polynomial forms using multiple sets of variables. Evaluations of the performance of the proposed algorithm are given. An example of multiple parallel computations of the terms of an arithmetic polynomial is analyzed. 相似文献
13.
WEI-PING WANG 《International journal of systems science》2013,44(9):1831-1839
A new approach with three novel operations is proposed to deal with analysis of linear and bilinear time-varying systems and optimal control of linear time-varying systems via the Taylor series. The use of the three operations: polynomial mapping, general multiplication and integral transformer can greatly simplify the algorithm derivations and computations. Recursive algorithms are obtained and several illustrative examples are given. 相似文献
14.
M. Arounassalame 《国际自动化与计算杂志》2012,9(1):81-86
In electrical circuit analysis, it is often necessary to find the set of all direct current (d.c.) operating points (either voltages or currents) of nonlinear circuits. In general, these nonlinear equations are often represented as polynomial systems. In this paper, we address the problem of finding the solutions of nonlinear electrical circuits, which are modeled as systems of n polynomial equations contained in an n-dimensional box. Branch and Bound algorithms based on interval methods can give guaranteed enclosures for the solution. However, because of repeated evaluations of the function values, these methods tend to become slower. Branch and Bound algorithm based on Bernstein coefficients can be used to solve the systems of polynomial equations. This avoids the repeated evaluation of function values, but maintains more or less the same number of iterations as that of interval branch and bound methods. We propose an algorithm for obtaining the solution of polynomial systems, which includes a pruning step using Bernstein Krawczyk operator and a Bernstein Coefficient Contraction algorithm to obtain Bernstein coefficients of the new domain. We solved three circuit analysis problems using our proposed algorithm. We compared the performance of our proposed algorithm with INTLAB based solver and found that our proposed algorithm is more efficient and fast. 相似文献
15.
16.
The Kovacic algorithm and its improvements give explicit formulae for the Liouvillian solutions of second order linear differential equations. Algorithms for third order differential equations also exist, but the tools they use are more sophisticated and the computations more involved. In this paper we refine parts of the algorithm to find Liouvillian solutions of third order equations. We show that, except for four finite groups and a reduction to the second order case, it is possible to give a formula in the imprimitive case. We also give necessary conditions and several simplifications for the computation of the minimal polynomial for the remaining finite set of finite groups (or any known finite group) by extracting ramification information from the character table. Several examples have been constructed, illustrating the possibilities and limitations. 相似文献
17.
The authors present a computer method of piecewise polynomial approximation of functions and solution of Cauchy problem for systems of ordinary differential equations based on the Newton polynomial. The approximating polynomial on a subinterval is converted to the form with numerical coefficients, the degree of the polynomial and the number of subintervals varies. The method is shown to uniformly converge at the rate of geometric progression under conditions of double continuous differentiability of the function and of the right-hand side of the system. The approximate solution of the system is continuous, continuously differentiable, and is characterized by low error rate, in particular, when solving stiff problems. 相似文献
18.
We briefly survey several existing methods for solving polynomial systems with inexact coefficients, then introduce our new symbolic-numeric method which is based on the geometric (Jet) theory of partial differential equations. The method is stable and robust. Numerical experiments illustrate the performance of the new method. 相似文献
19.
This paper presents a solution to the discrete-time optimal control problem for stochastic nonlinear polynomial systems over linear observations and a quadratic criterion. The solution is obtained in two steps: the optimal control algorithm is developed for nonlinear polynomial systems by considering complete information when generating a control law. Then, the state estimate equations for discrete-time stochastic nonlinear polynomial system over linear observations are employed. The closed-form solution is finally obtained substituting the state estimates into the obtained control law. The designed optimal control algorithm can be applied to both distributed and lumped systems. To show effectiveness of the proposed controller, an illustrative example is presented for a second degree polynomial system. The obtained results are compared to the optimal control for the linearized system. 相似文献
20.
We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other
two major subjects of algebraic and numerical computing, that is, computations with structured matrices and solving a system
of polynomial equations. In the first part of our paper, we extend the Toeplitz and Hankel structures of matrices and some
of their known properties to some new classes of structured (quasi-Hankel and quasi-Toeplitz) matrices, naturally associated
to systems of multivariate polynomial equations. In the second part of the paper, we prove some relations between these structured
matrices, which extend the classical relations of the univariate case.
Supported by NSF Grant CCR 9625344 and PSC CUNY Awards Nos. 667340 相似文献