Algorithms of discretization of algebraic spatial curves on homogeneous cubical grids

In this paper new methods of discretization (integer approximation) of algebraic spatial curves in the form of intersecting surfaces P(x, y, z) = 0 and Q(x, y, z) = 0 are analyzed.

The use of homogeneous cubical grids G(h³) to discretize a curve is the essence of the method. Two new algorithms of discretization (on 6-connected grid G_6c(h³) and 26-connected grid G₂₆(h³)) are presented based on the method above. Implementation of the algorithms for algebraic spatial curves is suggested. The elaborated algorithms are adjusted for application in computer graphics and numerical control of machine tools.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

The discrete collocation method for Fredholm–Hammerstein integral equations based on moving least squares method

The purpose of this paper is to investigate the discrete collocation method based on moving least squares (MLS) approximation for Fredholm–Hammerstein integral equations. The scheme utilizes the shape functions of the MLS approximation constructed on scattered points as a basis in the discrete collocation method. The proposed method is meshless, since it does not require any background mesh or domain elements. Error analysis of this method is also investigated. Some numerical examples are provided to illustrate the accuracy and computational efficiency of the method.     

A simple solution to the l optimization problem

It is pointed out in this brief paper that the l¹ optimization problem min_{Q ε lqp¹} | H − U * Q * V |₁, H ε l_mn¹, U ε l_mq¹, V ε l_pn¹ can be solved in one step rather than two. The solution of the dual problem is obviated by the direct solution of the primal problem via linear programming. The method here is applicable to finite-dimensional problems or approximating finite-dimensional problems, in the general case.     

Moving least squares collocation method for Volterra integral equations with proportional delay

In this work, we apply the moving least squares (MLS) method for numerical solution of Volterra integral equations with proportional delay. The scheme utilizes the shape functions of the MLS approximation constructed on scattered points as a basis in the discrete collocation method. The proposed method is meshless, since it does not require any background mesh or domain elements. An error bound is obtained to ensure the convergence and reliability of the method. Numerical results approve the efficiency and applicability of the proposed method.     

Quasi-steady friction in transient polytropic flow

An accurate method of integrating quasi-steady friction in transient polytropic flows is introduced and is justified both physically and analytically. When applied to subsonic flows, it is found to be especially informative at higher Mach numbers where existing methods of integration can lead to serious errors in mass conservation. The method is used herein to assess the accuracy of widely used finite difference representations of quasi-steady friction, attention focusing principally on solutions obtained using the method of characteristics.

The new method is exact in the special case of steady flows. Of the approximate methods considered, the popular approximation V_t¦V_{t − Δt}¦Δt is found to perform well. A modification introduced by Karney and McInnis (Journal of Hydology Engineering, ACSE, 1992, 118(7), 1014–1030 [1]) improves the correlation for downstream characteristic lines, but has the opposite effect for upstream characteristics. A simple cubic scheme, loosely related to a more complex one used successfully by Murray (Proceedings of the International Conference on Unsteady Flow and Fluid Transients, 29 September–1 October. Balkema, Amsterdam, 1992, pp. 143–157 [2]), illustrates difficulties in higher-order schemes.

The new method is not exact in transient flows, but it gives good accuracy in slowly varying flows and it is plausible in rapidly varying flows. Using it as a benchmark, the approximation V_t¦V_{t − Δt}¦Δt is again shown to perform well. All of the schemes considered are unreliable when the flow is about to become choked within the region of integration     

Parameter identification of linear multi-delay systems via a hybrid of block-pulse functions and Taylor’s polynomials

In this paper, an efficient and effective procedure is successfully developed for parameter identification of linear time-invariant multi-delay systems. The proposed framework is based on a hybrid of block-pulse functions and Taylor’s polynomials. Two upper error bounds corresponding to hybrid functions are established. The excellent properties of these functions together with the associated operational matrices of integration and delay are utilised to transform the original problem into a system of linear algebraic equations. The least squares method is then implemented for estimation of the unknown parameters. Several numerical experiments are investigated to demonstrate the usefulness and effectiveness of the proposed procedure. Easy implementation, simple operations and accurate solutions are the main features of the suggested approximation scheme.     

Computation of generalised inverse of a special class of matrices

The computation of the generalised Inverse A⁺ of matrix A depends critically of the rank of A and involves several matrix multiplications. It is shown here that if A is of the form where A_i are now vectors, then A⁺ can be computed efficiently and accurately by a simple algebraic method.     

Bivariate hermite subdivision

A subdivision scheme for constructing smooth surfaces interpolating scattered data in R³ is proposed. It is also possible to impose derivative constraints in these points. In the case of functional data, i.e., data are given in a properly triangulated set of points {(x_i, y_i)}_i=1^N from which none of the pairs (x_i,y_i) and (x_j,y_j) with i≠j coincide, it is proved that the resulting surface (function) is C¹. The method is based on the construction of a sequence of continuous splines of degree 3. Another subdivision method, based on constructing a sequence of splines of degree 5 which are once differentiable, yields a function which is C² if the data are not ‘too irregular’. Finally the approximation properties of the methods are investigated.     

从所需校正网络相频或幅频曲綫計算传递函数的方法

本文提供了一种从所需校正网络相频或幅频曲线计算校正网络传递函数的方法.利用最小二乘法的变形,通过解线性代数方程组可以得到传递函数系数的最或然值.本文提供的公式适合于用数字电子计算机计算.     

A complete algebraic solvability test for the nonstrict Lyapunov inequality

For arbitrary equally sized square complex matrices A and Q (Q Hermitian), the paper provides a complete algebraic test for verifying the existence of a Hermitian solution X of the nonstrict Lyapunov inequality A^*X + XA + Q 0. If existing, we exhibit how to construct a solution. Our approach involves the validation problem for the linear matrix inequality Σ_j=1^k (A_j^*X_jB_j + B_j^*X_j^*A_j) + Q> 0 in X_j, for which we provide an algebraic solvability test and a construct solutions if the kernels of A_j or, dually, those of B_j form an isotonic sequence.     

Local integration of population dynamics via moving least squares approximation

This paper applies an approach based on the Galerkin and collocation methods so-called meshless local Petrov–Galerkin (MLPG) method to treat a nonlinear partial integro-differential equation arising in population dynamics. In the proposed method, the MLPG method is applied to the interior nodes while the meshless collocation method is used for the nodes on the boundary, so the Dirichlet boundary condition is imposed directly. In MLPG method, it does not require any background integration cells so that all integrations are carried out locally over small quadrature domains of regular shapes, such as circles or squares in two dimensions and spheres or cubes in three dimensions. The moving least squares approximation is proposed to construct shape functions. A one-step time discretization method is employed to approximate the time derivative. To treat the nonlinearity, a simple predictor–corrector scheme is performed. Also the integral term, which is a kind of convolution, is treated by the cubic spline interpolation. Convergence in both time and spatial discretizations is shown and more, stability of the method is illustrated.     

Theories of contact specified by connection matrices

We begin by characterizing notions of geometric continuity represented by connection matrices. Next we present a set of geometric properties that must be satisfied by all reasonable notions of geometric continuity. These geometric requirements are then reinterpreted as an equivalent collection of algebraic constraints on corresponding sets of connection matrices. We provide a general technique for constructing sets of connection matrices satisfying these criteria and apply this technique to generate many examples of novel notions of geometric continuity. Using these constraints and construction techniques, we show that there is no notion of geometric continuity between reparametrization continuity of order 3, (G³), and Frenet frame continuity of order 3, (F³); that there are several notions of geometric continuity between G⁴ and F⁴; and that the number of different notions of geometric continuity between Gⁿ and Fⁿ grows at least exponentially with n.     

Optimized refinable enclosures of multivariate polynomial pieces

An enclosure is a two-sided approximation of a uni- or multivariate function by a pair of typically simpler functions such that b⁻bb⁺ over the domain U of interest. Enclosures are optimized by minimizing the width max_Ub⁺−b⁻ and refined by enlarging the space . This paper develops a framework for efficiently computing enclosures for multivariate polynomials and, in particular, derives piecewise bilinear enclosures for bivariate polynomials in tensor-product Bézier form. Runtime computation of enclosures consists of looking up pre-optimized enclosures and linearly combining them with the second differences of b. The width of these enclosures scales by a factor 1/4 under midpoint subdivision.     

基于方程建立和小波配置的模拟电路自动建模

提出一种模拟电路行为级自动建模的方法．通过构建节点代数方程确定系统结构描述,利用小波配置方法建立所有基本单元的行为级描述,最终建立系统行为级模型,并据此开发了自动建模软件．所建模型面向模拟电路硬件描述语言的工业标准形式,在保证较高精度的同时,在仿真速度上与晶体管级描述相比具有明显的优势．     

Integration of beam functions

The beam functions satisfying d⁴φ/dξ⁴ = β⁴φ with the associated boundary conditions are convenient admissible comparison functions for the approximated solutions of complex structural problems by the well known Rayleigh-Ritz method. Reliable integration formulae for products of various beam functions φ and ψ with an arbitrary function θ are essential. Felgar's recurrence formula for ∫ θφψ dξ is found to be in error and is corrected here. The condition when the characteristic values of θ and ψ are identical is also considered. A simple subroutine is given to evaluate ∫ θ(ξ)(dⁿφ/dξⁿ)(d^mψ/dξ^mdξ for all possible sets of boundary conditions. Applications to the free vibration of nonuniform beams and plate systems are demonstrated.     

High-order implicit blending surfaces of low degree

The applicability of the so-called potential method for blending implicitly defined surfaces is extended. The extended method is able to produce blendings which are C^k-continuous, where k may be chosen arbitrarily large. The blendings consist of piecewise algebraic surfaces of low degree. Specifically, the degree is k + 1 for so-called convex corners, and 2k for an important class of non-convex corners. In general the degree is linear in k, the constant of proportionality depending on the geometry of the corner. The method is illustrated by a concrete example, where a C² blending surface of degree 4 is constructed for a certain non-convex corner.     

Least squares support vector regression for solving Volterra integral equations

In this paper, a numerical approach is proposed based on least squares support vector regression for solving Volterra integral equations of the first and second kind. The proposed method is based on using a hybrid of support vector regression with an orthogonal kernel and Galerkin and collocation spectral methods. An optimization problem is derived and transformed to solving a system of algebraic equations. The resulting system is discussed in terms of the structure of the involving matrices and the error propagation. Numerical results are presented to show the sparsity of resulting system as well as the efficiency of the method.

     

An approximation algorithm for the solution of the nonlinear Lane-Emden type equations arising in astrophysics using Hermite functions collocation method

In this paper we propose a collocation method for solving some well-known classes of Lane-Emden type equations which are nonlinear ordinary differential equations on the semi-infinite domain. They are categorized as singular initial value problems. The proposed approach is based on a Hermite function collocation (HFC) method. To illustrate the reliability of the method, some special cases of the equations are solved as test examples. The new method reduces the solution of a problem to the solution of a system of algebraic equations. Hermite functions have prefect properties that make them useful to achieve this goal. We compare the present work with some well-known results and show that the new method is efficient and applicable.     

An iterative method for computing multivariate C piecewise polynomial interpolants

This paper describes a successive overrelaxation (SOR) method for computing a multivariate C¹ piecewise polynomial interpolant. Given a collection of points in R^m together with a triangulation of those points, the scheme described requires only the values of the function to be interpolated at the given points. The result is a C¹ interpolant whose restriction to each of the triangles in the triangulation is a polynomial of degree n.