Computing Derivatives of Noisy Signals Using Orthogonal Functions Expansions

In many applications noisy signals are measured. These signals have to be filtered and, sometimes, their derivative has to be computed. In this paper a method for filtering the signals and computing the derivatives is presented. This method is based on expansion onto transformed Legendre polynomials. Numerical examples demonstrate the efficacy of the method as well as the theoretical estimates. This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1364/04) and the UNITED STATES-ISRAEL BINATIONAL SCIENCE FOUNDATION (grant No. 2004099).     

High-Order Embedded Finite Difference Schemes for Initial Boundary Value Problems on Time Dependent Irregular Domains

This paper considers a family of spatially discrete approximations, including boundary treatment, to initial boundary value problems in evolving bounded domains. The presented method is based on the Cartesian grid embedded Finite-Difference method, which was initially introduced by Abarbanel and Ditkowski (ICASE Report No. 96-8, 1996; and J. Comput. Phys. 133(2), 1997) and Ditkowski (Ph.D. thesis, Tel Aviv University, 1997), for initial boundary value problems on constant irregular domains. We perform a comprehensive theoretical analysis of the numerical issues, which arise when dealing with domains, whose boundaries evolve smoothly in the spatial domain as a function of time. In this class of problems the moving boundaries are impenetrable with either Dirichlet or Neumann boundary conditions, and should not be confused with the class of moving interface problems such as multiple phase flow, solidification, and the Stefan problem. Unlike other similar works on this class of problems, the resulting method is not restricted to domains of up to 3-D, can achieve higher than 2nd-order accuracy both in time and space, and is strictly stable in semi-discrete settings. The strict stability property of the method also implies, that the numerical solution remains consistent and valid for a long integration time. A complete convergence analysis is carried in semi-discrete settings, including a detailed analysis for the implementation of the diffusion equation. Numerical solutions of the diffusion equation, using the method for a 2nd and a 4th-order of accuracy are carried out in one dimension and two dimensions respectively, which demonstrates the efficacy of the method. This research was supported by the Israel Science Foundation (grant No. 1362/04).     

Homotopy perturbation method for solving sixth-order boundary value problems

In this paper, we apply the homotopy perturbation method for solving the sixth-order boundary value problems by reformulating them as an equivalent system of integral equations. This equivalent formulation is obtained by using a suitable transformation. The analytical results of the integral equations have been obtained in terms of convergent series with easily computable components. Several examples are given to illustrate the efficiency and implementation of the homotopy perturbation method. Comparisons are made to confirm the reliability of the homotopy perturbation method. We have also considered an example where the homotopy perturbation method is not reliable.     

Strang-type preconditioners for solving linear systems from neutral delay differential equations

We study the solution of neutral delay differential equations (NDDEs) by using boundary value methods (BVMs). The BVMs require the solution of nonsymmetric, large and sparse linear systems. The GMRES method with Strang-type block-circulant preconditioner is proposed to solve these linear systems. We show that, if an -stable BVM is used for solving a system of NDDEs, then our preconditioner is invertible and the spectrum of the preconditioned system is clustered. It follows that, when the GMRES method is applied to the preconditioned systems, the method can converge rapidly. Numerical results are given to show that our method is effective. Received: July 2002 / Accepted: December 2002 RID="*" ID="*"The research of this author is supported by research grant No. RG024/01-02S/JXQ/FST from the University of Macau.     

Water resource quality monitoring using heterogeneous data and high-performance computations

This article presents the architecture of a system that is used for regional water resource quality monitoring of environmental parameters using heterogeneous data sources such as remote sensing data, model data, and data of in-situ observations. The system’s architecture and components are developed that are reusable and can be applied to solving various monitoring problems. The monitoring of the aquatic environment of the Dnieper estuary is selected as an example of such a problem. The distinctive features of this system consist of using a Grid approach to the distribution of complex computations and also the realization of computationally complicated computations on supercomputers of the SKIT family. Typical components of the monitoring system are presented, namely, those of data acquisition, data processing, modeling, and result representation. The development of the described monitoring system is partially supported by the UNTTs-NANU grant “Development of efficient Grid technologies of ecological monitoring on the basis of satellite data” (project No. 3872) and also joint INTAS-CNES-NSAU grant No. 06-1000024-9154 “Data Fusion Grid Infrastructure.” __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 179–188, July–August 2008.     

Solving linear and nonlinear initial value problems by the projected differential transform method

In this work, we propose a novel computational algorithm for solving linear and nonlinear initial value problems by using the modified version of differential transform method (DTM), which is called the projected differential transform method (PDTM). The PDTM can be easily applied to the initial value problems with less computational work. For the several illustrative examples, the computational results are compared with those obtained by many other methods; the Adomian decomposition, the variational iteration and the spline method. For all examples, the PDTM provides exact solutions. It has been shown that the PDTM is a reliable algorithm in obtaining analytic as well as approximate solution for the initial value problems.     

H_∞ controller synthesis of piecewise discrete time linear systems

This paper presents an H∞ controller design method for pieccwise discrete time linear systems based on a piecewise quadratic Lyapunov function. It is shown that the resulting closed loop system is globally stable with guaranteed H∞ perfomiance and the controller can be obtained by solving a set of bilinear lnatrLx inequalities. It has been shown that piecewise quadratic Lyapunov functions are less conservative than the global qnadnmc Lyapunov functions. A simulation example is also given to illustrate the advantage of the proposed approach.     

The Equivalence between Ordinal Optimization in Deterministic Complex Problems and in Stochastic Simulation Problems

In the last decade ordinal optimization (OO) has been successfully applied in many stochastic simulation-based optimization problems (SP) and deterministic complex problems (DCP). Although the application of OO in the SP has been justified theoretically, the application in the DCP lacks similar analysis. In this paper, we show the equivalence between OO in the DCP and in the SP, which justifies the application of OO in the DCP. Acknowledgment of Financial Support This work was supported by ARO contract DAAD19-01-1-0610, AFOSR contract F49620-01-1-0288, NSF grant ECS-0323685, NSFC Grant No.60274011 and the NCET (No.NCET-04-0094) program of China.     

Sinc-Galerkin method for solving nonlinear weakly singular two point boundary value problems

A study of Sinc-Galerkin method based on double exponential transformation for solving a class of nonlinear weakly singular two point boundary value problems with non-homogeneous boundary conditions is given. The properties of the Sinc-Galerkin approach are utilized to reduce the computation of nonlinear problem to nonlinear system of equations with unknown coefficients. This method tested on several test examples. We compare our numerical results with several numerical results of existing methods. The demonstrated results confirm that proposed method is considerably efficient, accurate nature and rapidly converge.     

An efficient method for solving nonlinear singular initial value problems

In [M.M. Hosseini, Modified Adomain decomposition method for specific second order ordinary differential equations, Appl. Math. Comput. 186 (2007), pp. 117–123] an efficient modification of Adomian decomposition method has been proposed for solving some cases of ordinary differential equations. In this paper, this method is generalized to more cases. The proposed method can be applied to linear, nonlinear, singular and nonsingular problems. Here, it is focused on nonlinear singular initial value problems of ordinary differential equations. The scheme is tested for some examples and the obtained results demonstrate reliability and efficiency of the proposed method.     

Fast and Stable Polynomial Equation Solving and Its Application to Computer Vision

This paper presents several new results on techniques for solving systems of polynomial equations in computer vision. Gröbner basis techniques for equation solving have been applied successfully to several geometric computer vision problems. However, in many cases these methods are plagued by numerical problems. In this paper we derive a generalization of the Gröbner basis method for polynomial equation solving, which improves overall numerical stability. We show how the action matrix can be computed in the general setting of an arbitrary linear basis for ?[x]/I. In particular, two improvements on the stability of the computations are made by studying how the linear basis for ?[x]/I should be selected. The first of these strategies utilizes QR factorization with column pivoting and the second is based on singular value decomposition (SVD). Moreover, it is shown how to improve stability further by an adaptive scheme for truncation of the Gröbner basis. These new techniques are studied on some of the latest reported uses of Gröbner basis methods in computer vision and we demonstrate dramatically improved numerical stability making it possible to solve a larger class of problems than previously possible.     

High-order compact boundary value method for the solution of unsteady convection–diffusion problems

In this paper, we propose a new class of high-order accurate methods for solving the two-dimensional unsteady convection–diffusion equation. These techniques are based on the method of lines approach. We apply a compact finite difference approximation of fourth order for discretizing spatial derivatives and a boundary value method of fourth order for the time integration of the resulted linear system of ordinary differential equations. The proposed method has fourth-order accuracy in both space and time variables. Also this method is unconditionally stable due to the favorable stability property of boundary value methods. Numerical results obtained from solving several problems include problems encounter in many transport phenomena, problems with Gaussian pulse initial condition and problems with sharp discontinuity near the boundary, show that the compact finite difference approximation of fourth order and a boundary value method of fourth order give an efficient algorithm for solving such problems.     

Variational iteration method for singular perturbation initial value problems

In this paper, the variational iteration method (VIM) is applied to solve singular perturbation initial value problems (SPIVPs). The obtained sequence of iterates is based on the use of Lagrange multipliers. Some convergence results of VIM for solving SPIVPs are given. Moreover, the illustrative examples show the efficiency of the method.     

A hybrid splitting method for variational inequality problems with separable structure

Alternating direction method (ADM), which decomposes a large-scale original variational inequality (VI) problem into a series of smaller scale subproblems, is very attractive for solving a class of VI problems with a separable structure. This type of method can greatly improve the efficiency, but cannot avoid solving VI subproblems. In this paper, we propose a hybrid splitting method with variable parameters for separable VI problems. Specifically, the proposed method solves only one strongly monotone VI subproblem and a well-posed system of nonlinear equations in each iteration. The global convergence of the new method is established under some standard assumptions as those in classical ADMs. Finally, some preliminary numerical results show that the proposed method performs favourably in practice.     

A novel method for nonlinear singular fourth order four-point boundary value problems

In this paper, a novel method is proposed for solving nonlinear singular fourth order four-point boundary value problems (BVPs) by combining advantages of the homotopy perturbed method (HPM) and the reproducing kernel method (RKM). Some numerical examples are presented to illustrate the strength of the method.     

Second-order two-point boundary value problems using the variational iteration algorithm-II

In this paper, we introduce an improved variational iteration method (VIM) for nonlinear second-order boundary value problems. The main advantage of this modification is that it can avoid additional computation in determining the unknown parameters in initial approximation when solving boundary value problems using the conventional VIM. Also, iterative sequences obtained using the improved VIM do satisfy the boundary conditions while iterative sequences obtained using conventional VIM may not, in general, satisfy the boundary conditions. Numerical results reveal that the improved method is accurate and efficient.     

Applied p-median and p-center algorithms for facility location problems

Facility location problems with the objective to minimize the sum of the setup cost and transportation cost are studied in this paper. The setup and transportation costs are considered as a function of the number of opened facilities. Three methods are introduced to solve the problem. The facility location model with bounds for the number of opened facility is constructed in this work. The relationship between setup cost and transportation cost is studied and used to build these methods based on greedy algorithm, p-median algorithm and p-center algorithm. The performance of the constructed methods is tested using 100 random data sets. In addition, the networks representing the road transportation system of Chiang Mai city and 5 provinces in Northern Thailand are illustrated and tested using all presented methods. Simulation results show that the method developed from greedy algorithm is suitable for solving problems when the setup cost is higher than transportation cost while the opposite cases are more efficiently solved with the method developed by the p-median problem.     

A full multigrid method for the Steklov eigenvalue problem

ABSTRACT

This paper introduces a kind of parallel multigrid method for solving Steklov eigenvalue problem based on the multilevel correction method. Instead of the common costly way of directly solving the Steklov eigenvalue problem on some fine space, the new method contains some boundary value problems on a series of multilevel finite element spaces and some steps of solving Steklov eigenvalue problems on a very low dimensional space. The linear boundary value problems are solved by some multigrid iteration steps. We will prove that the computational work of this new scheme is truly optimal, the same as solving the corresponding linear boundary value problem. Besides, this multigrid scheme has a good scalability by using parallel computing technique. Some numerical experiments are presented to validate our theoretical analysis.     

Translation separability of sets of polygons

We consider the problem of separating a set of polygons by a sequence of translations (one such collision-free translation motion for each polygon). If all translations are performed in a common direction the separability problem so obtained has been referred to as the uni-directional separability problem; for different translation directions, the more general multi-directional separability problem arises. The class of such separability problems has been studied previously and arises e.g. in computer graphics and robotics. Existing solutions to the uni-directional problem typically assume the objects to have a certain predetermined shape (e.g., rectangular or convex objects), or to have a direction of separation already available. Here we show how to compute all directions of unidirectional separability for sets of arbitrary simple polygons.The problem of determining whether a set of polygons is multi-directionally separable had been posed by G.T. Toussaint. Here we present an algorithm for solving this problem which, in addition to detecting whether or not the given set is multidirectionally separable, also provides an ordering in which to separate the polygons. In case that the entire set is not multi-directionally separable, the algorithm will find the largest separable subset.Research supported by NSERC under grant No. A9173 and A0392, respectively     

Numerical techniques for solving systems of second order boundary value problems

In this paper, we compare some collocation, finite difference and spline methods for solving a system of second order boundary value problems associated with obstacle problems. An example is given to illustrate the efficiency of these results.