An Algorithm to Compute the Exponential Part of a Formal Fundamental Matrix Solution of a Linear Differential System

In this paper we describe an efficient algorithm, fully implemented in the Maple computer algebra system, that computes the exponential part of a formal fundamental matrix solution of a linear differential system having a singularity of pole type at the origin. Received July 5, 1994; revised version March 21, 1996     

A Resultant Theory for the Systems of Two Ordinary Algebraic Differential Equations

 A notion of resultant in determinantal form of two ordinary algebraic differential equations is introduced and some properties are shown. This notion extends the analogous one given in the linear homogeneous case by Berkovich and Tsirulik in 1986 and it can be used for the elimination of variables and their derivatives. Received: September 29, 1995; revised version: August 2, 1996/January 4, 1997     

Computing the Galois Group of a Linear Differential Equation of Order Four

In 1978 J. Kovacic described an efficient algorithm for computing liouvillian solutions of a linear homogeneous differential equation of order two over a field C(x), where x′ = 1 and C is an algebraically closed field of characteristic 0. During the years from 1990 to 1994 M. Singer and F. Ulmer published several papers in which they describe efficient algorithms for determining the Galois group of such a differential equation of order two or three and computing liouvillian solutions using this group. In this paper we present results concerning Galois groups of order four linear differential equations. In particular we construct a list of irreducible linear algebraic subgroups of SL(4, C) where C is an algebraically closed field of characteristic zero. This list is complete up to conjugation, and in the finite primitive case, up to projective equivalence. Then, in keeping with the spirit of the work of Kovacic, Singer and Ulmer we use representation theory to distinguish between the groups in this list. Received: December 21, 1998; revised version: May 20, 2000     

Fitting Systems of Linear Differential Equations Using Computer Generated Exact Derivatives

The problem of estimating coefficients and initial values in a system of linear differential equations from observations on linear combinations of the system's responses is addressed. Using the Gauss-Newton algorithm, the reqllired function values are obtained by expressing the system's solution in terms of the eigenvalues and eigenvectors of its coefficient matrix aud its initial values. Differentiating this solution gives expressious for the required function derivatives in terms of these same eigenvalues and eigenvectors. The advantage of this approach is that it, uses exact analytic expressions for the required function values and derivatives rather than resorting to numerical integration or secants. An application to compartment, analysis is considered aud results are compared with those obtained by using the SAAM program of Berman and Weiss.     

Formal methods: The next generation of system design tools

Because of the growing demand for increasingly complex computer-based systems there is now an urgent need to provide tools to assist during the design of such systems. Formal specifications and formal methods provide such assistance but their widespread adoption has been hindered by the so-called ‘math fear’ and the perception that the tools are too difficult, too time consuming and too costly to use in a commercial environment. The aim of this article is to dispel the mystery surrounding the topic and to explain what formal methods are, how and why they are used, the benefits that accrue and why the technology should be accepted on a broader front. The application of formal methods to the design of computer-based systems will be discussed without resorting to jargon or mathematics. The discussion will concentrate more on the software content of systems but the arguments apply equally well to hardware. Some of the available tools will also be introduced.     

Note on Niederreiter-Xing's Propagation Rule for Linear Codes

We present a simple construction of long linear codes from shorter ones. Our approach is related to the product code construction; it generalizes and simplifies substantially the recent “Propagation Rule” by Niederreiter and Xing. Many optimal codes can be produced by our method. Received: June 23, 2000     

A Subspace-Projected Approximate Matrix Method for Systems of Linear Equations

Given two $n×n$ matrices $A$ and $A_0$ and a sequence of subspaces$\{0\}=\mathscr{V}_0⊂···⊂\mathscr{V}_n=\mathbb{R}^n$with dim$(\mathscr{V}_k)=\mathscr{k}$, the $k$-th subspace-projected approximated matrix $A_k$ is defined as $A_k=A+Π_k(A_0−A)Π_k$, where $Π_k$ is the orthogonal projection on $\mathscr{V}_{k}^⊥$. Consequently, $A_{k}v=Av$ and $v^{∗}A_{k}=v^{∗}A$ for all $v∈\mathscr{V}_{k}$. Thus $(A_{k})^{n}_{k≥0}$ is a sequence of matrices that gradually changes from $A_0$ into $A_n=A$. In principle, the definition of $\mathscr{V}_{k+1}$may depend on properties of $A_k$,which can be exploited to try to force $A_{k+1}$ to be closer to $A$ in some specific sense. By choosing $A_0$ as a simple approximation of $A$, this turns the subspace-approximated matrices into interesting preconditioners for linear algebra problems involving $A$. In the context of eigenvalue problems, they appeared in this role in Shepard et al. (2001), resulting in their Subspace Projected Approximate Matrix method. In this article, we investigate their use in solving linear systems of equations $Ax=b$. In particular, we seek conditions under which the solutions $x_k$ of the approximate systems $A_kx_k=b$ are computable at low computational cost, so the efficiency of the corresponding method is competitive with existing methods such as the Conjugate Gradient and the Minimal Residual methods. We also consider how well the sequence $(x_k)_{k≥0}$ approximates $x$, by performing some illustrative numerical tests.     

A Bound for the Order of Characteristic Set Elements of an Ordinary Prime Differential Ideal and some Applications

With respect to an elimination ordering, we give an upper bound for the order of characteristic set elements of an ordinary prime differential ideal. Using some results of complexity in the algebraic case, we show that computing characteristic sets of ordinary prime differential ideals, by change of ordering, is single exponential time. Received: January 8, 1997; revised version: May 6, 1999     

A Koszul Decomposition for the Computation of Linear Syzygies

In the present paper some algorithms are proposed for computing Linear Strands and Betti Numbers of graded modules over polynomial rings. These algorithms are based on a block-decomposition, induced by the Koszul syzygies, of the linear systems involved with the Hilbert's method for computing syzygies. Some further optimizations are suggested and applied by the authors to an implementation they have developed of the algorithms. Received: January 10, 2000; revised version: July 17, 2000     

Using Invariants to Solve the Equivalence Problem for Ordinary Differential Equations

Two given ordinary differential equations (ODEs) are called equivalent if one can be transformed into the other by a change of variables. The equivalence problem consists of two parts: deciding equivalence and determining a transformation that connects the ODEs. Our motivation for considering this problem is to translate a known solution of an ODE to solutions of ODEs which are equivalent to it, thus allowing a systematic use of collections of solved ODEs. In general, the equivalence problem is considered to be solved when a complete set of invariants has been found. In practice, using invariants to solve the equivalence problem for a given class of ODEs may require substantial computational effort. Using Tresse's invariants for second order ODEs as a starting point, we present an algorithmic method to solve the equivalence problem for the case of no or one symmetry. The method may be generalized in principle to a wide range of ODEs for which a complete set of invariants is known. Considering Emden-Fowler Equations as an example, we derive algorithmically equivalence criteria as well as special invariants yielding equivalence transformations. Received: May 26, 2000; revised version: September 6, 2000     

Parallel Solution of Linear Systems

Computational scientists generally seek more accurate results in shorter times, and to achieve this a knowledge of evolving programming paradigms and hardware is important. In particular, optimising solvers for linear systems is a major challenge in scientific computation, and numerical algorithms must be modified or new ones created to fully use the parallel architecture of new computers. Parallel space discretisation solvers for Partial Differential Equations (PDE) such as Domain Decomposition Methods (DDM) are efficient and well documented. At first glance, parallelisation seems to be inconsistent with inherently sequential time evolution, but parallelisation is not limited to space directions. In this article, we present a new and simple method for time parallelisation, based on partial fraction decomposition of the inverse of some special matrices. We discuss its application to the heat equation and some limitations, in associated numerical experiments.     

On the Structure of Linear and Cyclic Codes over a Finite Chain Ring

We generalise structure theorems of Calderbank and Sloane for linear and cyclic codes over ℤ _pa to a finite chain ring. Our results are more detailed and do not use non-trivial results from Commutative Algebra. Received: January 25, 1999; revised version: November 17, 1999     

用于自主车绕障的超声传感器线阵

根据超声波的作用机理和两种类型回波的不同振幅模式，设计了一种使于工程实现的超声传感器线阵。由该线阵采集到 数据，经过一简洁的经验专家系统，可以确定自主车前方障碍物的距离和方位。实验表明该线阵能成功地引导自主车绕过障碍物。     

Formal design and analysis of a hybrid supervisory control structure for Virtual Production Systems

Virtual Production Systems (VPSs) is a dynamic paradigm for production resources structure, which was proposed to cope with changing and uncertain manufacturing environment. However, the high performance of VPSs relies on a high-quality control in practice. Motivated by both local quick responses and global optimization, a supervisory control structure based on autonomous and coordination mechanisms is proposed for VPSs in this paper. This hybrid supervisory control structure is formally designed and analysed with timed automata on the platform of an integrated tool named UPPAAL. First, the Discrete Events Dynamic Systems (DEDS) model of VPSs is established. Then autonomous and coordinated supervisory controllers are further designed under the guidance of heuristic scheduling rules, such that the desired characteristics of both performance (production flow and time) and activity (overflow-, conflict- and deadlock-free) can be ensured. Finally, system analysis, including deadlock-free analysis, calculation and simulation of time-optimal scheduling, is made through verification. A case study is made to illustrate that control and scheduling can be well integrated into this hybrid supervisory control structure in practice.     

Some Power Mappings with Low Differential Uniformity

 Differentially uniform power mappings of the form f (x)=x ^d over GF(p ⁿ ) are considered. We construct an infinite family of 2-uniform mappings in the binary case. In the nonbinary case we give two large families of k-uniform mappings with low values of k. We also show how to construct families of sequences from differentially 1-uniform power mappings, which have parameters as good as the best presently known comparable families of sequences. Received: November 4, 1996; revised version: February 14, 1997     

Multiresponse Estimation With Special Application to Linear Systems of Differential Equations

We present a multiresponse estimation procedure for parameters of systems described by ? = As. The procedure features a generalized Gauss–Newton algorithm for optimizing the determinant criterion, efficient evaluation of the expectation function and its derivatives directly from the reaction network or compartment diagram, automatic determination of starting values, and eficient computational procedures for handling linear constraints on the responses.     

The Cell Method: an Enriched Description of Physics Starting from the Algebraic Formulation

In several recent papers studying the Cell Method (CM), which is a numerical method based on a truly algebraic formulation, it has been shown that numerical modeling in physics can be achieved even without starting from differential equations, by using a direct algebraic formulation. In the present paper, our focus will be above all on highlighting some of the theoretical features of this algebraic formulation to show that the CM is not simply a new numerical method among many others, but a powerful numerical instrument that can be used to avoid spurious solutions in computational physics.     

Projective Systems Whose Support is the Union of Two Linear Subspaces with Nonempty Intersection

We consider the code corresponding to a projective system whose support is the union of two linear subspaces with nonempty intersection, and prove that the code is uniquely determined up to equivalence by its weight enumerator. Also we obtain the same conclusion for the complement of the union of two linear subspaces.The authors are supported by Korea Research Foundation Grant (KRF-2001-005-D00002).     

A Criterion for Annihilating Ideals of Linear Recurring Sequences over Galois Rings

Let R be a local Artin principal ideal ring, R[x] the polynomial ring over R with indeterminate x. Let π be an element of R such that <π> is the unique maximal ideal of R. Let I be a zero-dimensional ideal of R[x], and the radical ideal of I. In this paper we show that I is the annihilating ideal of a linear recurring sequence over R if and only if I satisfies the following formula