EASY-FIT: a software system for data fitting in dynamical systems

EASY-FIT is an interactive software system to identify parameters in explicit model functions, steady-state systems, Laplace transformations, systems of ordinary differential equations, differential algebraic equations, or systems of one-dimensional time-dependent partial differential equations with or without algebraic equations. Proceeding from given experimental data, i.e. observation times and measurements, the minimum least squares distance of measured data from a fitting criterion is computed, that depends on the solution of the dynamical system. The software system is implemented in form of a Microsoft Access database running under MS-Windows 95/98/NT/2000. The underlying numerical algorithms are coded in Fortran and are executable independently from the interface. Model functions are either interpreted and evaluated symbolically by a Fortran-similar modeling language, that allows in addition automatic differentiation of nonlinear functions, or by user-provided Fortran subroutines. Received December 30, 2000     

PCC中数组边界检查的优化和生成

PCC的数组边界检查存在着由于无法确定数组下标表达式符号值的范围，而造成拒绝执行一些安全的移动代码等问题。本文给出的一种数组边界检查的优化及生成算法，不仅能够比较好地解决了这一问题，同时还生成了循环不变式注解中的条件谓词。我们设计的编译器——认证编译器——已经实现了这些算法，并完成了从用C编程语言的类型安全子集编写的源程序到携带注解的Intelx86／linux汇编语言程序的编译过程。由于基于语言安全策略系统的证明是建立在携带注解的代码基础之上的，因此该认证编译器中实现的算法在移动代码安全检查中非常有用。     

A mixed strategy of combining evolutionary algorithms with multigrid methods

Multigrid methods have been proven to be an efficient approach in accelerating the convergence rate of numerical algorithms for solving partial differential equations. This paper investigates whether multigrid methods are helpful to accelerate the convergence rate of evolutionary algorithms for solving global optimization problems. A novel multigrid evolutionary algorithm is proposed and its convergence is proven. The algorithm is tested on a set of 13 well-known benchmark functions. Experiment results demonstrate that multigrid methods can accelerate the convergence rate of evolutionary algorithms and improve their performance.     

An Optimizing Pascal Compiler

The architecture of a production optimizing compiler for Pascal is described, and the structure of the optimizer is detailed. The compiler performs both interprocedural and global optimizations, in addition to optimization of basic blocks. We have found that a high-level structured language such as Pascal provides unique opportunities for effective optimization, but that standard optimization techniques must be extended to take advantage of these opportunities. These issues are considered in our discussion of the optimization algorithms we have developed and the sequence in which we apply them.     

An extension of FORTRAN containing finite difference operators

Design of a language (PDELAN) to assist the programming of finite difference approximations to partial differential equations is described. A key part of the language is the representation of finite difference operators. The language is an extension of FORTRAN and is implemented as a preprocessor to a FORTRAN compiler.     

Algorithm optimization using a rule-based system. A case study: The Direct Kinematic Solution in robotics

The computation burden of intensive numerical real-time algorithms is a problem encountered in robotics and many other fields. A cost-effective solution for the implementation of these algorithms requires knowledge of computer architecture, compiler technology and algorithms. A cost-effective numeric processing methodology using a combined hardware-software approach and taking advantage of logic programming tools is presented. The methodology is based on optimizing the numerical calculation process of the algorithm. It also enables the specification of hardware resources. The process uses a rule-based-system (RBS) implemented in the logic programming language Prolog to automatically reduce the number of operations in the numerical execution of the algorithm and optimizes the use of hardware resources. The methodology provides a solution for the problems of handshake overhead and algorithm translation efficiency.The Direct Kinematics Solution (DKS), a robot arm control algorithm, is presented as a case study to illustrate the methodology. The proposed methodology has a general potential which can be extended to the optimization or implementation of different algorithms.     

ELSIM—a problem-solving environment for electrochemical kinetic simulations. Version 3.0-solution of governing equations associated with interfacial species,independent of spatial coordinates or in one-dimensional space geometry

A third version of the program ELSIM (for IBM compatible PCs) for the simulation of electrochemical transient methods has been elaborated upon. The program has been equipped with numerical algorithms that allow solution of kinetic problems characterized by the presence of interfacial species. Problems of this kind play an important role in electrochemical kinetic studies, among others in connection with electrocatalysis, modified electrodes or oscillatory systems. The user-written governing equations may take the form of differential—algebraic equations (for the concentrations of interfacial species) independent of spatial coordinates, or partial differential equations (for the concentrations of bulk species) in one-dimensional space geometry, coupled with differential—algebraic equations. Problem formulation has also been facilitated by the inclusion of a reaction compiler, which automatically generates the text of the above governing equations for user-written reaction mechanisms. Other new features include an option for the least-squares fitting of simulated transients to experimental curves, a hypertext help facility, and enhanced performance owing to the revised formula translation based on the three-address internal code generation, and on automatic differentiation.     

Mumbo: A Rule-Based Implementation of a Run-time Program Generation Language

We describe our efforts to use rule-based programming to produce a model of Jumbo, a run-time program generation (RTPG) system for Java. Jumbo incorporates RTPG following the simple principle that the regular compiler — or, rather, its back-end — can be used both for ordinary, static compilation and for run-time compilation. This tends to produce a run-time compiler that is inefficient but potentially subject to improvement by partial evaluation. However, the complexity of the language and compiler have made it difficult for us to achieve actual optimization. The model, written in Maude, preserves all the essential ingredients of Jumbo, but operates on a simplified language, called Mumbo. The simplification in the language together with Maude's support for code rewriting has allowed us to make rapid progress. We discuss the model in detail, the kinds of optimizations we have obtained, and the impact on the Jumbo project.     

The application of gradient-only optimization methods for problems discretized using non-constant methods

We study the minimization of objective functions containing non-physical jump discontinuities. These discontinuities arise when (partial) differential equations are discretized using non-constant methods and the resulting numerical solutions are used in computing the objective function. Although the functions may become discontinuous, gradient information may be computed at every point. Gradient information is computable everywhere since every point has an associated discretization for which (semi) analytical sensitivities can be calculated. Rather than the construction of global approximations using only function value information to overcome the discontinuities, we propose to use only the gradient information. We elaborate on the modifications of classical gradient based optimization algorithms for use in gradient-only approaches, and we then present gradient-only optimization strategies using both BFGS and a new spherical quadratic approximation for sequential approximate optimization (SAO). We then use the BFGS and SAO algorithms to solve three problems of practical interest, both unconstrained and constrained.     

Parallel multilevel methods with adaptivity on unstructured grids

We present two parallel multilevel methods for solving large-scale discretized partial differential equations on unstructured 2D/3D grids. The presented methods combine three powerful numerical algorithms: overlapping domain decomposition, multigrid method and adaptivity. As the foundation of the methods we propose an algorithm for generating and partitioning a hierarchy of adaptively refined unstructured grids, so that adaptivity can be incorporated up to a certain grid level. We ensure that the resulting subgrid hierarchies are well balanced and no inter-processor communication is needed across different grid levels, thus obtaining high parallel efficiency. Numerical experiments show that the parallel multilevel methods offer almost equally fast convergence as their sequential multigrid counterpart. And the resulting implementation has reasonably good scalability. Received: 4 December 1998 / Accepted: 12 January 2000     

Design of maximum thrust plug nozzles with variable inlet geometry

An optimization analysis is presented for axisymmetric plug nozzles with varible inlet geometry. The analysis is based on the governing gas dynamic relations for a rotational flow of a frozen or equilibrium gas mixture. The problem is formulated to maximize the axial thrust produced by the plug nozzle for a general isoperimetric constraint, such as constant nozzle length or constant nozzle surface area. The effects of base pressure and ambient pressure are included in the thrust expression to be maximized. The governing gas dynamic equations and the differential and integral constraints that the solution must satisfy are incorporated into the formulation by means of Lagrange multiples. The formalism of the calculus of variations is applied to the resulting functional to be maximized. The results of the optimization analysis are a set of partial differential equations for determining the Lagrange multipliers in the region of interest and a set of equations for determining the necessary boundary conditions for the solution. The complete set of equations for the gas dynamic properties and the Lagrange multipliers are system of first order, quasi-linear, non-homogeneous partial differential equations of the hyperbolic type, which can be treated by the method of charac- teristics. The characteristic and compatibility equations for the system are presented. A numerical solution procedure is presented to determine wether or not a given plug nozzle geometry is an optimal solution. An iteration technique is developed which systematically adjusts the plug nozzle geometry until the optimal solution is obtained. Selected parametric studies are presented. These studies illustrate the effect of the specific heat ratio, the design pressure ratio and the base pressure model on the thrust peformance and nozzle geometry of optimal, fixed length, plug nozzles.     

On the applicability of the longest-match rule in lexical analysis

The lexical analyzer of a compiler usually adopts the longest-match rule to resolve ambiguities when deciding the next token in the input stream. However, that rule may not be applicable in all situations. Because the longest-match rule is widely used, a language designer or a compiler implementor frequently overlooks the subtle implications of the rule. The consequence is either a flawed language design or a deficient implementation. We propose a method that automatically checks the applicability of the longest-match rule and identifies precisely the situations in which that rule is not applicable. The method is useful to both language designers and compiler implementors. In particular, the method is indispensable to automatic generators of language translation systems since, without the method, the generated lexical analyzers can only blindly apply the longest-match rule and this results in erroneous behaviors. The crux of the method consists of two algorithms: one is to compute the regular set of the sequences of tokens produced by a nondeterministic Mealy automaton when the automaton processes elements of an input regular set. The other is to determine whether a regular set and a context-free language have nontrivial intersection with a set of equations.     

Solving equations by hybrid evolutionary computation techniques

Evolutionary computation techniques have mostly been used to solve various optimization and learning problems. This paper describes a novel application of evolutionary computation techniques to equation solving. Several combinations of evolutionary computation techniques and classical numerical methods are proposed to solve linear and partial differential equations. The hybrid algorithms have been compared with the well-known classical numerical methods. The experimental results show that the proposed hybrid algorithms outperform the classical numerical methods significantly in terms of effectiveness and efficiency     

A little language for modularizing numerical PDE solvers

This paper describes a concise specification language for linear partial differential equations (PDEs) on a union of rectangles, along with three tools: a pretty-printer, TEX generator, and a code generator. The pretty-printer and TEX generator help users by allowing equations to be specified (and read) in their natural form, while the code generator allows implementors to separate their numerical solver from the input equations, and greatly simplifies testing. Copyright © 2004 John Wiley & Sons, Ltd.     

应用Calerkin方法辨识一维抛物型偏微分方程及其边界条件中的参数

本文提出了一种一维抛物型偏微分方程及其边界条件中定常参数的辨识方法.这一方法 将所研究的偏微分方程初-边值问题转化为具有已知初值的常微分方程组问题,然后再利用最 优化方法将参数估算出来.数值仿真与实验验证都表明这一辨识方法是可行的.     

Introduction to variational image-processing models and applications

Variational image-processing models offer high-quality processing capabilities for imaging. They have been widely developed and used in the last two decades, enriching the fields of mathematics as well as information science. Mathematically, several tools are needed: energy optimization, regularization, partial differential equations, level set functions, and numerical algorithms. This special issue presents readers with nine excellent research papers covering topics from research work into variational image-processing models, algorithms and applications, including image denoising, image deblurring, image segmentation, image reconstruction, restoration of mixed noise types and three-dimensional surface restoration.     

Lattice Boltzmann Models for Anisotropic Diffusion of Images

The lattice Boltzmann method has attracted more and more attention as an alternative numerical scheme to traditional numerical methods for solving partial differential equations and modeling physical systems. The idea of the lattice Boltzmann method is to construct a simplified discrete microscopic dynamics to simulate the macroscopic model described by the partial differential equations. The use of the lattice Boltzmann method has allowed the study of a broad class of systems that would have been difficult by other means. The advantage of the lattice Boltzmann method is that it provides easily implemented fully parallel algorithms and the capability of handling complicated boundaries. In this paper, we present two lattice Boltzmann models for nonlinear anisotropic diffusion of images. We show that image feature selective diffusion (smoothing) can be achieved by making the relaxation parameter in the lattice Boltzmann equation be image feature and direction dependent. The models naturally lead to the numerical algorithms that are easy to implement. Experimental results on both synthetic and real images are described.     

Equational programming in λ-calculus via SL-systems. Part 2

A system of equations in the λ-calculus is a set of formulas of Λ (the equations) together with a finite set of variables of Λ (the unknowns). A system s is said to be β-solvable (βη-solvable) iff there exists a simultaneous substitution with closed λ-terms for the unknowns that makes the equations of s theorems in the theory β (βη). A system s can be viewed as a set of specifications (the equations) for a finite set of programs (the unknowns) whereas a solution for s yields executable codes for such programs.

A class of systems for which the solvability problem is effectively decidable defines an equational programming language and a system solving algorithm for defines a compiler for such language.

This leads us to consider separation-like systems (SL-systems), i.e. systems with equations having form , wherex is an unknown and z is a free variable which is not an unknown.

It is known that the β (βη)-solvability problem for SL-systems is undecidable.

Here we show that there is a class of SL-systems (NP-regular SL-systems) for which the β-solvability problem is NP-complete. Moreover, we show that any SL-system s can be transformed into an NP-regular SL-system s. This transformation consists of adding abstractions to the LHS occurrences of the RHS variables of s. In this sense NP-regular SL-systems isolate the source of undecidability for SL-systems, namely: a shortage of abstractions on the LHS occurrences of the RHS variables.

NP-regular SL-systems yield an equational programming language in which unrestrained self-application is handled, constraints on executable code to be generated by the compiler can be specified by the user and (properties of) data structures can be described in an abstract way. However, existence of executable code satisfying a specification in such language is an NP-complete problem. This is the price we have to pay for allowing unrestrained self-application in our language.     

ELSIM—A PC program for electrochemical kinetic simulations. Version 2.0—solution of the sets of kinetic partial differential equations in one-dimensional geometry,using finite difference and orthogonal collocation methods

The second version of the program ELSIM (for an IBM compatible PC) for the simulation of electrochemical kinetic transients has been elaborated, based on the previously proposed method-oriented approach to the formulation of algorithms for electrochemical kinetic simulations. The program allows direct numerical solution of a large class of user-defined electrochemical kinetic partial differential equations (PDEs) in one-dimensional geometry, using a variety of standard finite difference techniques and orthogonal collocation. The rules of the simple PDE language and other aspects of the specification of kinetic problems and solution algorithms are presented and illustrated by examples.