| Special
Session Symbolic and Algebraic Computation for Optimization Tasks in Science and Engineering |
| Dmitry
Chibisov Victor Ganzha Ernst W. Mayr |
Lehrstuhl
für Effiziente Algorithmen Institut für Informatik Technische Universität München Boltzmannstr. 3 D-85748 Garching |
Various applications in robotics, manufacturing, molecular biology, nanotechnology, etc. involve optimization and optimal control with constraints given by algebraic and differential equations (both ODEs and PDEs). Especially in the case of differential constraints, the "naive" approaches combining numerical solvers for differential equations and optimization algorithms may lead to lack of robustness or be very inefficient. In order to deal with real life applications stability and fast convergence of numerical methods have to be provided. However, research in this field is very much in progress, and many problems concerning both the theoretical foundations and practical issues remain open: existence of optimizers for underlying continuous problem and necessary optimality conditions, questions of stability and convergence for numerical methods, the interplay between discretization and optimization, etc. These issues require a wide range of mathematical disciplines (e.g. optimal control theory, functional analysis, numerical analysis, etc.) as well as engineering understanding in order to choose the appropriate mathematical model for the problem at hand. The goal of this session is to bring together mathematicians and engineers, who develop or use algebraic and numerical methods, to exchange ideas and views, and to present both original research results involving computer algebra as well as challenging directions and industrial applications. Possible topics for this session include (but are not limited to):
to Dmytro Chibisov, Victor Ganzha, and Ernst Mayr by June 5. |
| 9:30-10:00 | Evangelos A. Coutsias, Michael J. Wester | Application of Dixon Resultants to Protein Structure Refinement Abstract: We consider the problem of loop closure, i.e., finding structures of a segment in a chain molecule that are geometrically consistent with the rest of the chain structure. In many situations of practical interest, such as the problem of homology modeling in proteins, the mathematical statement of this problem is to construct a polygonal line consisting of a given number of straight segments joining specified start and end points, such that the lengths of the segments and the angles between successive segments are given. Then, the only degrees of freedom in this construction are some of the dihedral (torsion) angles formed by successive segment triplets. This is a consequence of the fact that the energy associated with deforming certain dihedrals from their minimal energy configurations are orders of magnitude smaller than the energies associated with deforming bond lengths or bond angles. In fact, even some of the dihedrals, e.g., those associated with peptide bonds in a protein are ``hard'' as well, while the dihedrals associated with the bonds stemming from the central carbon atom in a residue (the phi and psi angles) are generally soft. It is well known that at least 6 free torsions are necessary for producing a localized deformation of a polygonal line with fixed angles. This is due essentially to the 6 affine degrees of freedom for placing a rigid object in 3-space. Several formulations of this problem, which is equivalent to the positioning of the end effector of a 6 degree of freedom robotic arm, exist, with the first solutions dating back to the pioneering work of Go and Scheraga in the 1970's. The most general solution known in the robotics literature allows arbitrary arrangements of the torsional axes. In the molecular context, it is often the case that pairs of freely rotatable bonds share a vertex (atom), making the formulation of the problem considerably simpler. Recently we proposed a general method of solving this problem when the 6 torsions are associated with 3 pairs of coterminal axes (meeting at points with arbitrary structure between the pairs. This formulation leads to a system of three biquadratic polynomials in terms of variables describing the orientation of the rigid units about virtual axes joining the points, which is a generalization of a system derived originally for the study of the conformation of octahedra. We present the reduction of this polynomial system to a univariate polynomial of degree 16 by means of the Dixon resultant. The implementation of this reduction with Maple is accomplished efficiently by first effecting certain algebraic simplifications as direct reductions proved to be intractable, leading to extraneous factors, whose presence led to a polynomial of degree 32. Moreover, the direct implementation masked the symmetry of the final form, which proved useful for deducing interesting geometric properties associated with certain special cases, such as the conformational problem of a 6-membered ring. |
|
| 10:00-10:30 | Veronika Pillwein |
Symbolic Summation Algorithms for High Order Finite Element Basis Functions Abstract: The finite element method (FEM) is a numerical method for solving partial differential equations on complicated domains. Via the finite element method the given partial differential equation is transformed into a linear system of equations. This usually large system is commonly solved by iterative methods. Their performance depends on properties of the system matrix such as a small condition number. Also of interest is a fast assemblance of the system matrix. These demands are influenced by a diligent choice of the basis functions. In this talk we present the construction of edge based and low energy vertex based basis functions for the high order finite element method. It has been shown that the application of cheap block-Jacobi preconditioners is efficient for the proposed bases. We will focus on demonstrating how recently developed computer algebra algorithms for symbolic summation can be used to derive recurrence relations allowing a simple implementation for fast basis function evaluation. |
|
| Coffee Break |
|||
| 11:00-11:30 | |||
| 11:30-12:00 | Dmitry Chibisov, Ernst W. Mayr | Computing Minimum Time Motion for 6R Robots Abstract: In this work we discuss the robot motion planning problem for multiple tasks distributed in space, which have to be executed by an robot with six revolution joints and describe an approach for computing the minimum-time robot motion due to given velocity and orientation of the robot end-effector during the task execution, and limits on velocities and accelerations during the overall work-cycle. Since the velocity of task execution is given, the time needed for execution of given tasks can be reduced using the freedom in orientation of the end-effector in such a way as to reduce the motion time between tasks. Since the optimization problem is highly nonlinear and no efficient methods for finding the global minimas are known, we describe the hierarchy of relaxations to this optimization task, for which the global minimum can be computed efficiently, and give an evaluation of different optimization methods with respect to the computed global minimum of the relaxed problems. |