Automatic Differentiation for MATLAB Programs

Derivative information is required in numerous applications, including sensitivity analysis and numerical optimization. For simple functions, symbolic differentiation–done either manually or with a computer algebra system–can provide the derivatives, whereas divided differences (DD) have been used traditionally for functions defined by (potentially very complex) computer programs, even if only approximate values can be obtained this way. An alternative approach for such functions is automatic differentiation (AD), yielding exact derivatives at often lower cost than DD, and without restrictions on the program complexity. In this paper we compare the functionality and describe the use of ADMIT/ADMAT and ADiMat. These two AD tools provide derivatives for programs written in the MATLAB language, which is widely used for prototype and production software in scientific and engineering applications. While ADMIT/ADMAT implements a pure operator overloading approach of AD, ADiMat also employes source transformation techniques.     

Experiments with a symbolic programming system for complex analysis

The paper reports the results of work on the construction of LISP programs for various symbolic operations in complex analysis, including the evaluation of integrals around closed contours by the use of Cauchy's Theorem. It is concluded that the only difficulty in the way of the preparation of programs for all of the important and useful textbook calculations in complex analysis is that large amounts of fast storage in the computer are needed.     

Symbolic computation of normal forms for semi-simple cases

This paper presents a method and computer programs for computing the normal forms of ordinary differential equations whose Jacobian matrix evaluated at an equilibrium involves semi-simple eigenvalues. The method can be used to deal with systems which are not necessarily described on a center manifold. An iterative procedure is developed for finding the closed-form expressions of the normal forms and associated nonlinear transformations. Computer programs using a symbolic computer language Maple are developed to facilitate the application of the method. The programs can be conveniently executed on a main frame, a workstation or a PC machine without any interaction. A number of examples are presented to demonstrate the applicability of the method and the computation efficiency of the Maple programs.     

Ergodicity and Accuracy of Optimal Particle Filters for Bayesian Data Assimilation

Data assimilation refers to the methodology of combining dynamical models and observed data with the objective of improving state estimation. Most data assimilation algorithms are viewed as approximations of the Bayesian posterior (filtering distribution) on the signal given the observations. Some of these approximations are controlled, such as particle filters which may be refined to produce the true filtering distribution in the large particle number limit, and some are uncontrolled, such as ensemble Kalman filter methods which do not recover the true filtering distribution in the large ensemble limit. Other data assimilation algorithms, such as cycled 3DVAR methods, may be thought of as controlled estimators of the state, in the small observational noise scenario, but are also uncontrolled in general in relation to the true filtering distribution. For particle filters and ensemble Kalman filters it is of practical importance to understand how and why data assimilation methods can be effective when used with a fixed small number of particles, since for many large-scale applications it is not practical to deploy algorithms close to the large particle limit asymptotic. In this paper, the authors address this question for particle filters and, in particular, study their accuracy (in the small noise limit) and ergodicity (for noisy signal and observation) without appealing to the large particle number limit. The authors first overview the accuracy and minorization properties for the true filtering distribution, working in the setting of conditional Gaussianity for the dynamics-observation model. They then show that these properties are inherited by optimal particle filters for any fixed number of particles, and use the minorization to establish ergodicity of the filters. For completeness we also prove large particle number consistency results for the optimal particle filters, by writing the update equations for the underlying distributions as recursions. In addition to looking at the optimal particle filter with standard resampling, they derive all the above results for (what they term) the Gaussianized optimal particle filter and show that the theoretical properties are favorable for this method, when compared to the standard optimal particle filter.     

Computation of the normal forms for general M-DOF systems using multiple time scales. Part I: autonomous systems

This paper is concerned with the symbolic computation of the normal forms of general multiple-degree-of-freedom oscillating systems. A perturbation technique based on the method of multiple time scales, without the application of center manifold theory, is generalized to develop efficient algorithms for systematically computing normal forms up to any high order. The equivalence between the perturbation technique and Poincaré normal form theory is proved, and general solution forms are established for solving ordered perturbation equations. A number of cases are considered, including the non-resonance, general resonance, resonant case containing 1:1 primary resonance, and combination of resonance with non-resonance. “Automatic” Maple programs have been developed which can be executed by a user without knowing computer algebra and Maple. Examples are presented to show the efficiency of the perturbation technique and the convenience of symbolic computation. This paper is focused on autonomous systems, and non-autonomous systems are considered in a companion paper.     

非牛顿流体非定常旋转流动计算机智能解析理论

计算机符号运算科学是人工智能的前沿方向。计算机软件Macsyma是完成符号运算的有力工具。应用德国Darmstadt大学的计算机软件Macsyma、与数学方法和流变学模型结合,研究了Oldroyd B流体由一类定常状态向另一定常状态转变的非定常流动过程。采用改进的Kantorovich方法和符号运算软件,把该问题的3阶偏微分方程的初、边值问题化为各级近似的2阶常微分方程问题。并给出了1级、2级和3级近似方程的解析形式解答。该研究表明了计算机符号处理解决应用数学和力学问题的潜力,同时指出了由一定常状态向另一定常状态转变的非牛顿流动过程,可以经历无限多途径,这一现象是由于本构方程的非线性性质引起的。     

Optimal economic production quantity policy for imperfect process with imperfect repair and maintenance

This study integrates maintenance and production programs with the economic production quantity (EPQ) model for an imperfect process involving a deteriorating production system with increasing hazard rate: imperfect repair and rework upon failure (out of control state). The imperfect repair performs some restorations and restores the system to an operating state (in-control state), but leaves its failure until perfect preventive maintenance (PM) is performed. There are two types of PM, namely imperfect PM and perfect PM. The probability that perfect PM is performed depends on the number of imperfect maintenance operations performed since the last renewal cycle. Mathematical formulas are obtained for deriving the expected total cost. For the EPQ model, the optimum run time, which minimizes the total cost, is discussed. Various special cases are considered, including the maintenance learning effect. Finally, a numerical example is presented to illustrate the effects of PM, setup, breakdown and holding costs.     

Symbolic models for infinite networks of control systems: A compositional approach

This paper presents a compositional framework for the construction of symbolic models for a network composed of a countably infinite number of finite-dimensional discrete-time control subsystems. We refer to such a network as infinite network. The proposed approach is based on the notion of alternating simulation functions. This notion relates a concrete network to its symbolic model with guaranteed mismatch bounds between their output behaviors. We propose a compositional approach to construct a symbolic model for an infinite network, together with an alternating simulation function, by composing symbolic models and alternating simulation functions constructed for subsystems. Assuming that each subsystem is incrementally input-to-state stable and under some small-gain type conditions, we present an algorithm for orderly constructing local symbolic models with properly designed quantization parameters. In this way, the proposed compositional approach can provide us a guideline for constructing an overall symbolic model with any desired approximation accuracy. A compositional controller synthesis scheme is also provided to enforce safety properties on the infinite network in a decentralized fashion. The effectiveness of our result is illustrated through a road traffic network consisting of infinitely many road cells.     

Automated knowledge source selection and service composition

We introduce a new combinatorial problem referred to as the component set identification problem, arising in the context of knowledge discovery, information integration, and knowledge source/service composition. The main motivation for studying this problem is the widespread proliferation of digital knowledge sources and services. Considering a granular knowledge domain consisting of a large number of individual bits and pieces of domain knowledge (properties) and a large number of knowledge sources and services that provide mappings between sets of properties, the objective of the component set identification problem is to select a minimum cost combination of knowledge sources that can provide a joint mapping from a given set of initially available properties (initial knowledge) to a set of initially unknown properties (target knowledge). We position the component set identification problem relative to other combinatorial problems and provide a classification scheme for the different variations of the problem. The problem is next modeled on a directed graph and analyzed in terms of its complexity. The directed graph representation is then augmented and transformed into a time-expanded network representation that is subsequently used to develop an exact solution procedure based on integer programming and branch-and-bound. We enhance the solver by developing preprocessing techniques. All findings are supported by computational experiments.     

Simulation and Measurements of Rolling Tire Dynamics

The simulation of rolling tires including stationary rolling, modal analysis, excitation with roughness of road surfaces and sound radiation is presented for state of the art industrial tire models. The target of this research, part of the german project “Leiser Straßenverkehr”, is the reduction of trafic noise, whereas the main source, namely the tire/road system, is investigated in contrast to other techniques like sound insulating walls. The needs and methods for the solution of the resulting large scale problems are discussed next to special properties of rotating structures, high frequency behavior of rubber material and approaches for the reduction of computational cost. For the validation of the model measurements of real tires and roads are used. These include shaker tests of the standing tire and acoustics of tires rolling on a drum. The same set–ups are applied to the simulation for the comparison of frequency response functions and sound pressure levels. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

城市医疗急救绩效分析研究

为了准确评估城市医疗急救(120急救)系统的救援绩效,面向救护车救援调度过程,通过将救护车状态定义为空闲或繁忙建立救护车队的救援状态空间,基于条件概率的乘法规则以及生灭过程平衡方程,构造求解各救护车工作强度(救护车处在繁忙状态的时间占比)的近似线性方程组及其迭代求解算法,由此提出了救护车工作强度近似模型。基于救护车工作强度,给出了救护车跨区救援比例、响应时间等救援绩效计算方法。为了验证上述模型,评价了苏州市区120急救系统的绩效指标,据此改善了救护车救援系统配置方案。研究表明,救护车工作强度近似模型克服了以往救护车数量较多时(大于20辆)难以求解的困难;根据救援距离设置救护车指派优先级能够实现救护车共享、平衡各救护车工作强度以及跨区救援比例;在不增加救护车总数的情况下,基于救援绩效能够改善救护车分布以及急救辖区划分从而有效缩短医疗急救响应时间。     

Symbolic Computation with Monotone Operators

We consider a class of monotone operators which are appropriate for symbolic representation and manipulation within a computer algebra system. Various structural properties of the class (e.g., closure under taking inverses, resolvents) are investigated as well as the role played by maximal monotonicity within the class. In particular, we show that there is a natural correspondence between our class of monotone operators and the subdifferentials of convex functions belonging to a class of convex functions deemed suitable for symbolic computation of Fenchel conjugates which were previously studied by Bauschke & von Mohrenschildt and by Borwein & Hamilton. A number of illustrative examples utilizing the introduced class of operators are provided including computation of proximity operators, recovery of a convex penalty function associated with the hard thresholding operator, and computation of superexpectations, superdistributions and superquantiles with specialization to risk measures.     

On the discrete kinetic theory for active particles. Mathematical tools

This paper deals with the development of a mathematical discrete kinetic theory to model the dynamics of large systems of interacting active particles whose microscopic state includes not only geometrical and mechanical variables (typically position and velocity), but also peculiar functions, called activities, which are able to modify laws of classical mechanics. The number of the above particles is sufficiently large to describe the overall state of the system by a suitable probability distribution over the microscopic state, while the microscopic state is discrete. This paper deals with a methodological approach suitable to derive the mathematical tools and structures which can be properly used to model a variety of models in different fields of applied sciences. The last part of the paper outlines some research perspectives towards modelling.     

Structural properties of optimal schedules with preemption

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions. When does an optimal schedule exist (provided that there are feasible schedules)? When does it have a finite/polynomial number of interruptions? Do they occur at integral/rational points only? These theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we answer some of these basic questions for a rather general scheduling model (including, as the special cases, the classicalmodels such as parallelmachine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of the objective functions including nearly all known. For some two special cases of objective functions (including, however, all classical ones), we prove the existence of an optimal solution with a special “rational structure.” An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP.     

Intelligent data analysis and model interpretation with spectral analysis fuzzy symbolic modeling

This paper proposes fuzzy symbolic modeling as a framework for intelligent data analysis and model interpretation in classification and regression problems. The fuzzy symbolic modeling approach is based on the eigenstructure analysis of the data similarity matrix to define the number of fuzzy rules in the model. Each fuzzy rule is associated with a symbol and is defined by a Gaussian membership function. The prototypes for the rules are computed by a clustering algorithm, and the model output parameters are computed as the solutions of a bounded quadratic optimization problem. In classification problems, the rules’ parameters are interpreted as the rules’ confidence. In regression problems, the rules’ parameters are used to derive rules’ confidences for classes that represent ranges of output variable values. The resulting model is evaluated based on a set of benchmark datasets for classification and regression problems. Nonparametric statistical tests were performed on the benchmark results, showing that the proposed approach produces compact fuzzy models with accuracy comparable to models produced by the standard modeling approaches. The resulting model is also exploited from the interpretability point of view, showing how the rule weights provide additional information to help in data and model understanding, such that it can be used as a decision support tool for the prediction of new data.     

Structural Analysis in the Dynamical Modelling of Chemical Engineering Systems

The dynamical modelling of physical (bio-)chemical processes based on first principles considerations is analysed from a structural point of view. Based on a classification of the variables and equations that occur in such models, we propose a general framework that can help to organise the model in a transparent way and to analyse efficiently its solv- ability properties. We show that a well-known tool in the theory of nonlinear dynamical systems, the Zero Dynamics Algorithm, can be used in the analysis of higher index mod- els and also in index reduction. The symbolic computations involved in this algorithm are readily available in the form of nonlinear system analysis packages. The proposed methods are illustrated by a few simple concrete examples. Keywords : First principles modelling, differential-algebraic systems, index reduction.     

The imbedded state space approach to reducing dimensionality in dynamic programs of higher dimensions

By exploiting discontinuity properties of the maximal convolution it is possible to drastically reduce dimensionality in finite dynamic programs. In fact, we show how the search over the usual M-dimensional state space can be reduced to a one-dimensional search over an imbedded state space. The versatility of our approach is illustrated on a number of example problems.     

Mathematical tools of the kinetic theory of active particles with some reasoning on the modelling progression and heterogeneity

The mathematical approach proposed in this paper refers to the modelling, and related mathematical problems, of large systems of interacting entities whose microscopic state includes not only geometrical and mechanical variables (typically position and velocity), but also peculiar functions or specific activities. The number of the above entities is sufficiently large for describing the overall state of the system using a suitable probability distribution over the microscopic state. The first part of the paper is devoted to the derivation of suitable mathematical structures which can be properly used to model a variety of models in different fields of applied sciences. Then some research perspectives are analyzed, focussed on applications to biological systems.     

Using algebraic models of programs for detecting metamorphic malwares

Polymorphic and metamorphic viruses are the most sophisticated malicious programs that give a lot of trouble to virus scanners. Each time when these viruses infect new executables or replicate themselves, they completely modify (obfuscate) their signature to avoid being detected. This contrivance poses a serious threat to antivirus software that relies on classical virus-detection techniques: such viruses do not have any stable specific sequence of instructions that one looks for. In the ultimate case, the only characteristic that remains invariable for all generations of the same virus is their functionality (semantics). To all appearance, the only way to detect for sure a metamorphic malicious code is to look for a pattern that has the same semantics as (i.e., equivalent to) some representative sample of the virus. Thus, metamorphic virus detection is closely related to the equivalence-checking problem for programs. In this paper, we outline some new automata-theoretic framework for the designing of virus detectors. Our approach is based on the equivalence-checking techniques in algebraic models of sequential programs. An algebraic model of programs is an abstract model of computation, where programs are viewed as finite automata operating on Kripke structures. Models of this kind make it possible to focus on those properties of program instructions that are widely used in obfuscating transformations. We give a survey (including the latest results) on the complexity of equivalence-checking problem in various algebraic models of programs and estimate thus the resilience of some obfuscating transformation commonly employed by metamorphic viruses.