Localized algorithms for vlsi processor arrays

In this paper we analyze the algorithms expressed as a system of recurrence equations. The algorithms are called 2^?1 output algorithms if two output values of one function (variable identification) are specified by the system of recurrence equations for each index point in the algorithm. The algorithm is in free form if the indexes of these two values are not dependent. Two standard classes are determined by this criteria: the nearest neighbour and the all pair form. For example the sorting algorithm can be expressed in the all pair form i.e., the linear insertion algorithm or in the nearest neighbour form i.e., the bubble sort algorithm. However these algorithms are different in their nature. A procedure to eliminate the computational broadcast for the all pair 2^?1output algorithm has been proposed by the authors in [1]. The result obtained by implementing this procedure was a localized form of the algorithm and a system of uniform recurrence equations by eliminating the computational and data broadcast. So he data dependence method can be efficiently used for parallel implementations. The proposed procedure cannot be implemented directly on the nearest neighbour form algorithms. Here we show how the algorithm can be restructured into a form where the computational and data broadcast can be eliminated. These transformations result in localized algorithms. A few examples show how these algorithms can be implemented on processor arrays. For example, the Gentleman Kung triangular array [2] can be used for solving the QR decomposition algorithm for both forms of the algorithm. The implementations differ in the order of the data flow and the processor operation. We show that the implementation of the nearest neighbour algorithm is even better than the standard one.     

The new extended Jacobian elliptic function expansion algorithm and its applications in nonlinear mathematical physics equations

More recently we have presented the extended Jacobian elliptic function expansion method and its algorithm to seek more types of doubly periodic solutions. Based on the idea of the method, by studying more relations among all twelve kinds of Jacobian elliptic functions. we further extend the method to be a more general method, which is still called the extended Jacobian elliptic function expansion method for convenience. The new method is more powerful to construct more new exact doubly periodic solutions of nonlinear equations. We choose the (2+1)-dimensional dispersive long-wave system to illustrate our algorithm. As a result, twenty-four families of new doubly periodic solutions are obtained. When the modulus m→1 or 0, these doubly periodic solutions degenerate as soliton solutions and trigonometric function solutions. This algorithm can be also applied to other nonlinear equations.     

A numerical method for solving systems of linear and nonlinear integral equations of the second kind by hat basis functions

In this paper, we use hat basis functions to solve the system of Fredholm integral equations (SFIEs) and the system of Volterra integral equations (SVIEs) of the second kind. This method converts the system of integral equations into a linear or nonlinear system of algebraic equations. Also, we consider the order of convergence of the method and show that it is O(h²). Application of the method on some examples show its accuracy and efficiency.     

A relation between Newton and Gauss-Newton steps for singular nonlinear equations

The Gauss-Newton step belonging to an appropriately chosen bordered nonlinear system is analyzed. It is proved that the Gauss-Newton step calculated after a sequence of Newton steps is equal to the doubled Newton step within the accuracy ofO(‖x?x ^*‖²). The theoretical insight given by the proof can be exploited to derive a Gauss-Newton-like algorithm for the solution of singular equations.     

A series solution algorithm for initial boundary-value problems with variable properties

A multiple infinite trigonometric cum polynomial series method for solving initial-boundary value problems governed by hyperbolic differential equations with variable coefficients is developed. The method proposed herein can be easily applied to a broad class of engineering systems including those cases where boundary conditions may vary with time. In the proposed mathematical technique, the solution form is assumed as a combination of infinite Fourier series and polynomial series of nth order, where n is the order of the differential equation. The coefficients of the polynomial series are obtained as functions of undetermined Fourier series coefficients by satisfying the initial-boundary conditions. The variable coefficients are expanded in appropriate half-range sine or cosine series. Insertion of the above Fourier-polynomial series solutions into the differential equation and application of orthogonality conditions leads to a linear summation equation which can be solved in open form. However, the authors have developed a closed-form series solution consisting of a highly efficient algorithm. The major advantage of this technique is the development of a solution algorithm, coupled with the multiple infinite trigonometric cum polynomial series solutions, leading to fast converging series solutions. A representative initial and boundary value problem governed by hyperbolic partial differential equations of variable coefficients is presented herein to demonstrate the efficiency and accuracy of the method.     

三角Bézier曲面的几何约束形变

利用三角Bézier曲面的矩阵表达形式,把几何约束下的形状调整算法从曲线和张量积曲面推广到三角Bézier曲面,使得三角Bézier曲面在形变后既能保持外形大致不变,又能满足一系列事先指定的几何约束(点约束和法向约束).利用Lagange乘子法,几何约束形变的条件极值问题被转化为线性方程组的求解问题,以便于快速计算.特别地,三角Bézier曲面在形变前后还可以满足边界曲线在角点处保持(Ca,Cb,Cc)连续.数值实例表明,该算法简单有效,便于CAD(计算机辅助设计)系统进行交互.     

Identification of partial differential equation models for a class of multiscale spatio-temporal dynamical systems

In this article, the identification of a class of multiscale spatio-temporal dynamical systems, which incorporate multiple spatial scales, from observations is studied. The proposed approach is a combination of Adams integration and an orthogonal least squares algorithm, in which the multiscale operators are expanded, using polynomials as basis functions, and the spatial derivatives are estimated by finite difference methods. The coefficients of the polynomials can vary with respect to the space domain to represent the feature of multiple scales involved in the system dynamics and are approximated using a B-spline wavelet multi-resolution analysis. The resulting identified models of the spatio-temporal evolution form a system of partial differential equations with different spatial scales. Examples are provided to demonstrate the efficiency of the proposed method.     

Efficient computation of higher order frequency response functions for nonlinear systems with,and without,a constant term

The behaviour of a nonlinear system can be profoundly affected by the presence of a constant or dc term in the system governing equation. These changes are reflected in the nonlinear frequency response characteristics of the system which provide a powerful insight into the system's dynamics. In this article, a new and efficient algorithm is presented for computing the higher order Volterra frequency response functions from nonlinear time-domain models that may contain a constant term. A comparison with previous methods is included to demonstrate the significant gains in computational efficiency that are achieved using the new method. The algorithm is applicable to systems modelled by nonlinear differential, or difference, equations and is easily automated. Several examples are used to illustrate the method, and to highlight the importance of dc terms in nonlinear system analysis.     

Numerical studies on Boussinesq-type equations via a split-step Fourier method

Boussinesq-type nonlinear wave equations with dispersive terms are solved via split-step Fourier methods. We decompose the equations into linear and nonlinear parts, then solve them orderly. The linear part can be projected into phase space by a Fourier transformation, and resulting in a variable separable ordinary differential system, which can be integrated exactly. Next, by an invert Fourier transformation, the classical explicit fourth-order Runge–Kutta method is adopted to solve the nonlinear subproblem. To examine the numerical accuracy and efficiency of the method, we compare the numerical solutions with exact solitary wave solutions. Additionally, various initial-value problems for all the listed Boussinesq-type system are studied numerically. In the study, we can observe that sech ²-type waves for KdV-BBM system will split into several solitons, which is a very interesting physical phenomenon. The interaction between solitons, including overtaking and head-on collisions, is also simulated.     

An algorithm for system immersion into nonlinear observer form: SISO case

The class of nonlinear systems that can be put into nonlinear observer form (linear system with output injection) can be broadened if we employ the system immersion. We provide an immersion algorithm for SISO nonlinear systems with relative degree r. The proposed algorithm is an extension of the previous results and does not require the relative degree 1 assumption. In addition, it is seen that the immersion can always be computed via algebraic computations and simple integrations except in a very special case in which the relative degree equals the system dimension (in this case, only one first order differential equation appears in the algorithm).     

粒子群算法在求解方程组中的应用

提出了采用粒子群算法求解线性方程组和非线性方程组的智能算法。采用粒子群算法求解方程组具有形式简单、收敛迅速和容易理解等特点,且能在一次计算中多次发现方程组的解,可以解决非线性方程组多解的求解问题,为线性方程组和非线性方程组的求解提供了一种新的方法。     

K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations

This paper proposes a parallel algorithm,called KDOP (K-Dimensional Optimal Parallel algorithm),to solve a general class of recurrence equations efficiently.The KDOP algorithm partitions the computation into a series of subcomputations,each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task.The algorithm solves the equations in O(N/P) steps in EREW PRAM model (Exclusive Read Exclusive Write Parallel Random Access Machine model) using p≤N^1-∈ processors,where N is the size of the problem,and ∈ is a given constant.This is an optimal algorithm (its sepeedup is O(p)) in the case of p≤N^1-∈.Such an optimal speedup for this problem was previously achieved only in the case of p≤N^0.5.The algorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.     

The solution of multi-parameter systems of equations with application to problems in nonlinear elasticity

Systems of nonlinear equations governed by more than one parameter are discussed with particular attention to bifurcation behaviour. The procedure adopted is to add to the original system of n equations (m − 1) further equations, in the case of m parameters, and to seek solution curves in R^n+m to this augmented system. Two types of additional equations are considered: one describes a piecewise linear path in the space of parameters, and the second constrains the solution curve to be a locus of singular points. These ideas are all subsequently applied to the systems of equations arising from finite element approximations of boundary value problems in nonlinear elasticity. The behaviour of a nonlinear elastic thick-walled cylinder subjected to internal pressure and axial extension is discussed.     

Modeling and stability analysis of cascade buck converters with N power stages

This paper presents a method for stability analysis of N-cell cascade step-down buck converters, which is a kind of complex nonlinear system. A nonlinear model in the form of time-variant state equations is derived, and then the loop gain describing the overall system is introduced. With the help of them, we obtain the equations for phase cross over frequency and gain margin by small-signal perturbation technique, harmonic balance method, and inverse iteration method. Based on the equations, the overall cascade system stability can be analyzed regardless of the number of converters cascaded. Finally, the cascade buck converter with three power stages is used to demonstrate the effectiveness of the proposed stability analysis method.     

A quadratically convergent method for computing simple singular roots and its application to determining simple bifurcation points

We present an efficient method for computing roots of mappings on ? ⁿ in the case where the Jacobian has the rankn?1 at the root. For the accurate determination of such a rootx*∈? ⁿ an auxiliary system ofn equations inn+1 variables is constructed which possesses (x ^*, 1) as a turning point. This turning point can be computed by direct methods. We use an adapted method which requires only the solution of (n+1)-dimensional systems of linear equations and the evaluation of one Jacobian and 5 function values per step. This techniques is successfully applied to compute simple bifurcation points by means of a suitable system of nonlinear equations which has the properties mentioned above.     

Application of nonlinear dynamic analysis to the identification and control of nonlinear systems-III. n-Dimensional systems

In two previous publications, the authors have shown that normal form theory, a method used extensively in dynamic analysis, can be applied in the structure identification of nonlinear systems. In particular, normal form theory bridges the gap between structure of a nonlinear, low order polynomial dynamical system and the behavior it is able to predict or represent. This is important because knowing a system's dynamic behavior automatically leads to a simple nonlinear normal form model that can be used for (nonlinear) control. Previously, only two-dimensional normal form models were derived. For this paper, simple, n-dimensional, low order polynomial dynamical models will be derived that can represent a nonlinear system with multiple steady states or a limit cycle in the operating region of interest. Using as a plant the nonisothermal Continuous Stirred Tank Reactor with consecutive reactions (A→B→C), it is shown that identification and control of this three-dimensional system using the aforementioned normal form models is feasible.     

A method and a software package for numerical solution of the systems of nonlinear ordinary integro-differential-algebraic equations

A method, an algorithm and a software package for automatically solving the ordinary nonlinear integro-differential-algebraic equations (IDAEs) of a sufficiently general form are described. The author understands an automatic solution as obtaining a result without carrying out the stages of selecting a method, programming, and program checking. Both initial and boundary value problems for such equations are solved. It is assumed that the complete set of boundary and initial conditions at the beginning of the integration interval are given. By performing differentiation, the system of IDAEs can be modified, in general, into a system of ordinary nonlinear differential equations (IDEs). The problem of finding the solution of the above-mentioned system on the uniform grid on the integration interval is posed in two forms: as solving the system of IDAEs and as solving the appropriate system of IDEs, where the developed program is to be used. In order to reduce the system of IDAEs and the system of IDEs to the systems of ordinary nonlinear algebraic equations, at every stage of the algorithm the integration and differentiation formulas obtained earlier by N.G. Bandurin are used. Systems similar to those test systems of both nonlinear IDAEs and IDEs considered in this investigation are solved by using the computer programs. It is evident that the coincidence of the results for one and the same system of equations in its different forms can serve as good evidence of the correctness of the obtained results.     

Control bifurcations

A parametrized nonlinear differential equation can have multiple equilibria as the parameter is varied. A local bifurcation of a parametrized differential equation occurs at an equilibrium where there is a change in the topological character of the nearby solution curves. This typically happens because some eigenvalues of the parametrized linear approximating differential equation cross the imaginary axis and there is a change in stability of the equilibrium. The topological nature of the solutions is unchanged by smooth changes of state coordinates so these may be used to bring the differential equation into Poincare/spl acute/ normal form. From this normal form, the type of the bifurcation can be determined. For differential equations depending on a single parameter, the typical ways that the system can bifurcate are fully understood, e.g., the fold (or saddle node), the transcritical and the Hopf bifurcation. A nonlinear control system has multiple equilibria typically parametrized by the set value of the control. A control bifurcation of a nonlinear system typically occurs when its linear approximation loses stabilizability. The ways in which this can happen are understood through the appropriate normal forms. We present the quadratic and cubic normal forms of a scalar input nonlinear control system around an equilibrium point. These are the normal forms under quadratic and cubic change of state coordinates and invertible state feedback. The system need not be linearly controllable. We study some important control bifurcations, the analogues of the classical fold, transcritical and Hopf bifurcations.     

圆弧拱的面内非线性动力学分析

对圆弧拱面内自由振动的频率和非线性内共振现象进行了研究.通过假设满足位移边界条件的振型函数对圆弧拱的面内非线性方程进行Galerkin一阶模态截断,先对派生系统的线性频率进行求解,就不同参数对频率的影响进行分析;然后利用多尺度法对离散模型进行求解.结果表明:截面高度对径向振动频率有显著影响,但是对切向振动频率影响很小;另外,就本文方程而言,可能存在三种内共振形式,但内共振现象的产生与否还决定于圆弧拱的边界条件.     

Global finite-time stabilization of a class of uncertain nonlinear systems

This paper studies the problem of finite-time stabilization for nonlinear systems. We prove that global finite-time stabilizability of uncertain nonlinear systems that are dominated by a lower-triangular system can be achieved by Hölder continuous state feedback. The proof is based on the finite-time Lyapunov stability theorem and the nonsmooth feedback design method developed recently for the control of inherently nonlinear systems that cannot be dealt with by any smooth feedback. A recursive design algorithm is developed for the construction of a Hölder continuous, global finite-time stabilizer as well as a C¹ positive definite and proper Lyapunov function that guarantees finite-time stability.