Search

The Small Exponent Test (SET) for exponentiation is an essential batch-verification technique that is widely applied. In this paper, we propose a simplified SET that can securely batch-verify n instances with only n − 1 randomizing exponents. We show that the structure of the proposed batch test is compact in the sense that it works with a minimal number of randomizing exponents for the SET. Thus, our test offers various advantages. Overall, compared to the original SET, the proposed simplified SET is more efficient for any sized batch instance. In particular, unlike the SET, our proposal performs well even when the size of a batch instance is small, e.g., n = 1 , 2 , 3 , and 4. This feature can be also used to significantly reduce pairing computations in a signature scheme where several pairing equations are verified. In addition, our test can be combined easily and generically with existing batch techniques such as the use of sparse exponents, the bucket test for large batch sizes, or an automated tool to generate a batch algorithm. Finally, with our simplified test, an efficient identification algorithm can be constructed to discover incorrect instances in a batch. [ABSTRACT FROM AUTHOR]

Abstract: The C-Algorithm introduced in is designed to determine isochronous centers for Lienard-type differential systems, in the general real analytic case. However, it has a large complexity that prevents computations, even in the quartic polynomial case. The main result of this paper is an efficient algorithmic implementation of C-Algorithm, called ReCA (Reduced C-Algorithm). Moreover, an adapted version of it is proposed in the rational case. It is called RCA (Rational C-Algorithm) and is widely used in to find many new examples of isochronous centers for the Liénard type equation. [Copyright &y& Elsevier]

Abstract: In this paper a hybrid configuration of a FACTS controller called Optimal Unified Power Flow Controller (OUPFC) which is composed of a mechanical phase shifting transformer augmented with a small scale Unified Power Flow Controller (UPFC) is introduced. The steady-state model of OUPFC is developed as a power injection model. This model is used to develop an Optimal Power Flow (OPF) algorithm including OUPFC to find the optimum number, location, and settings of OUPFCs to minimize the total fuel cost and power losses. Simulation results are presented for the IEEE 14-, 30-, and 118-bus systems. The optimization method is numerically solved using Matlab and General Algebraic Modelling System (GAMS) software environments. The results demonstrate the effectiveness of the proposed approach to solve the optimal location and settings of OUPFCs incorporated in OPF problem and improve the power system operation. Furthermore, the ability of OUPFC to optimize the objective functions is compared to that of PST and UPFC. [ABSTRACT FROM AUTHOR]

Abstract: Assessing the quality of ontologies is important to reuse/integrate ontologies. In this paper, we propose an approach to revise ontology inconsistency by measuring the relevant ontology constructs such as semantic partitions, axiom fanouts per concept, minimal incoherence-preserving subsets, incoherence impact value per axiom and preferable revision weight per concept in the ontology being measured. We also propose several algorithms to compute the measurement values of these ontology constructs, which can be used to pinpoint and rank which axioms and concepts are most likely to cause the ontology inconsistency. Our approach can help determine which concepts should be preferentially modified and therefore enables automatic revision of ontology inconsistency in the context of a dynamic and evolving environment. [Copyright &y& Elsevier]

Abstract: This paper presents a high-accuracy method for fine registration of two partially overlapping point clouds that have been coarsely registered. The proposed algorithm, which is named dual interpolating point-to-surface method, is principally a modified variant of point-to-surface Iterative Closest Point (ICP) algorithm. The original correspondences are established by adopting a dual surface fitting approach using B-spline interpolation. A novel auxiliary pair constraint based on the surface fitting approach, together with surface curvature information, is employed to remove unreliable point matches. The combined constraint directly utilizes global rigid motion consistency in conjunction with local geometric invariant to reject false correspondences precisely and efficiently. The experimental results involving a number of realistic point clouds demonstrate that the new method can obtain accurate and robust fine registration for pairwise 3D point clouds. This method addresses highest accuracy alignment with less focus on recovery from poor coarse registrations. [Copyright &y& Elsevier]

Abstract: Anisotropic mesh generation is important for interpolation and numerical modeling. Recently, Labelle and Shewchuk proposed a two-dimensional guaranteed-quality anisotropic mesh generation algorithm called a Voronoi refinement algorithm. This algorithm treats only domains with straight lines as inputs. In many applications, however, input domains have many curves and the exact representation of curves is required for efficient numerical modeling. In this paper, we extend the Voronoi refinement algorithm and propose it as a guaranteed-quality anisotropic mesh generation algorithm for domains with curved boundaries. Some experimental results are also shown. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to discuss the class of leap-frog-type neural learning algorithms having the unitary group of matrices as parameter space. In the discussed framework, each step of a learning algorithm computes as an unconstrained learning step followed by a projection step. The present manuscript focuses on projection methods and related implementation issues. Projection methods based on singular/eigenvalue matrix decomposition as well as on QR decomposition are discussed in details. Two possible ways to combine these projection methods, based on projection-operator composition and on geodesic mid-point interpolation, are also discussed and tested numerically. [Copyright &y& Elsevier]

Abstract: This paper presents the particular integral formulation for two (2D) and three (3D) dimensional transient dynamic elastoplastic analyses. The elastostatic equation is used for the complementary solution. The particular integrals for displacement, traction and stress rates are obtained by introducing the concept of a global shape function to approximate acceleration and initial stress rate terms of the inhomogeneous equation. The Houbolt time integration scheme is used for the time-marching process. The Newton–Raphson algorithm for plastic multiplier is used to solve the system equation. The developed program is integrated with the pre- and post-processor. Numerical results for four example problems are given to demonstrate the validity and accuracy of the present formulation. [Copyright &y& Elsevier]

Abstract: In this paper we propose an affine scaling interior algorithm via Lanczos path for solving nonlinear equality systems subject to bounds on variables. Employing the affine scaling Lanczos path search strategy, we obtain an iterative direction by solving the linearize model. By using the line search backtracking technique, we will find an acceptable trial step length along this direction which is strictly feasible and makes the objective function nonmonotonically decreasing. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. Furthermore, the numerical results of the proposed algorithm indicate to be effective. [Copyright &y& Elsevier]

Abstract: In this paper, a simple and efficient iterative algorithm is adopted to model crack closure and sliding with the displacement discontinuity method (DDM). The problem of a subsurface crack in a half-plane under indentation loading considered by Elvin and Leung (Elvin N, Leung C. A fast iterative boundary element method for solving closed crack problems. Engng Fract Mech 1999;63:631–48) and DeBremaecker and Ferris (DeBremaecker J-Cl, Ferris MC. A comparison of two algorithm for solving closed crack problems. Engng Fract Mech 2000;66:601–05) is reexamined using the iterative DDM. The cases of a partially closed crack with both frictionless and frictional contacts are considered. Benchmark results for the stress intensity factors and the interfacial crack mechanisms for a subsurface crack are presented and compared with the results obtained from the fast iterative algorithm of Elvin and Leung and those from the PATH algorithm of DeBremaecker and Ferris. [Copyright &y& Elsevier]

Abstract: This paper develops an efficient particle tracking algorithm to be used in fluid simulations approximated by a high-order multidomain discretization of the Navier–Stokes equations. We discuss how to locate a particle''s host subdomain, how to interpolate the flow field to its location, and how to integrate its motion in time. A search algorithm for the nearest subdomain and quadrature point, tuned to a typical quadrilateral isoparametric spectral subdomain, takes advantage of the inverse of the linear blending equation. We show that to compute particle-laden flows, a sixth-order Lagrangian polynomial that uses points solely within a subdomain is sufficiently accurate to interpolate the carrier phase variables to the particle position. Time integration of particles with a lower-order Adams–Bashforth scheme, rather than the fourth-order Runge–Kutta scheme often used for the integration of the carrier phase, increases computational efficiency while maintaining engineering accuracy. We verify the tracking algorithm with numerical tests on a steady channel flow and an unsteady backward-facing step flow. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new convergence rate for both symmetric and nonsymmetric positive definite problems. In our theory, “regularity and approximation” assumption is used. A new rate of convergence estimate with is used where α is a “regularity and approximation” parameter. Also, a new convergence rate is given by two-grid schemes. [Copyright &y& Elsevier]

Abstract: In this paper, a bilevel time minimizing assignment problem is studied in which the aim is to find an optimal partition of the set of n facilities into two mutually disjoint subsets L 1 and L 2 where, L 1 contains m facilities called Level-I facilities and L 2 contains the remaining (n − m) facilities termed as Level-II facilities. The partition is to be optimal in the sense that for this partition the sum of the completion times of the jobs assigned to Level-I and Level-II facilities is the least. It is assumed that all the jobs are to be done, each facility works only on one job, and on each job only one facility works. Further Level-II facilities start working simultaneously on their respective assigned jobs only after Level-I facilities, working in parallel, have finished their jobs. For a feasible assignment denotes the completion time of the jobs assigned to Level-I facilities and that of the jobs assigned to Level-II facilities. Depending on m is greater or smaller than (n − m), the pairs of the type and of the completion times of the jobs assigned to Level-I and Level-II facilities are generated and an optimal partition of the set of n facilities is determined corresponding to the pair for which is the least. To obtain the global minimizer of the proposed problem, a polynomial time algorithm is presented which has been coded in C++ and an empirical analysis has been carried out with the help of randomly generated test problems. [Copyright &y& Elsevier]

Abstract: In this paper we present some notes of the PageRank algorithm, including its L 1 condition number and some observation of the numerical tests of two variant algorithms which are based on the extrapolation method. [Copyright &y& Elsevier]

Abstract: In this paper we present a methodology for trimming 3D solid finite element meshes using a non-uniform rational B-spline (NURBS) surfaces representation. The algorithms applied in the identification of the spatial position of the finite element (FE) nodes and elements relative to the trimming surface are described, as well as, the explanation of the correction methods adopted to geometrically rearrange the trimmed elements. Three different strategies are proposed to adjust, with greater or lesser accuracy, the trimmed FE mesh to the trimming surface. The first consists only of an element elimination strategy, while the other two are based on a nodal stretching strategy, aiming for more accurate adjustment of the finite elements boundary to the trimming surface. Finally, to highlight the capabilities of the developed program, a mesh generation example is given by trimming a mesh with the shape of a blank automotive panel. [Copyright &y& Elsevier]

Abstract: Central schemes are frequently used for incompressible and compressible flow calculations. The present paper is the first in a forthcoming series where a new approach to a 2nd order accurate Finite Volume scheme operating on Cartesian grids is discussed. Here we start with an adaptively refined Cartesian primal grid in 3D and present a construction technique for the staggered dual grid based on -Voronoi cells. The local refinement constellation on the primal grid leads to a finite number of uniquely defined local patterns on a primal cell. Assembling adjacent local patterns forms the dual grid. All local patterns can be analysed in advance. Later, running the numerical scheme on staggered grids, all necessary geometric information can instantly be retrieved from lookup-tables. The new scheme is compared to established ones in terms of algorithmic complexity and computational effort. [Copyright &y& Elsevier]

Abstract: We propose a “fast” algorithm for the construction of a data-sparse inverse of a generalToeplitz matrix. The computational cost for inverting an N × N Toeplitz matrix equals the cost of four length-N FFTs plus an O(N)-term. This cost should be compared to the O(N log2 N) cost of previously published methods. Moreover, while those earlier methods are based on algebraic considerations, the procedure of this paper is analysis-based; as a result, its stability does not depend on the symmetry and positive-definiteness of the matrix being inverted. The performance of the scheme is illustrated with numerical examples. [Copyright &y& Elsevier]

Abstract: In this paper, a class of optimization problems with equality and inequality constraints is discussed. Firstly, the original problem is transformed to an associated simpler problem with only inequality constraints and a parameter. The later problem is shown to be equivalent to the original problem if the parameter is large enough (but finite), then a feasible descent SQP algorithm for the simplified problem is presented. At each iteration of the proposed algorithm, a master direction is obtained by solving a quadratic program (which always has a feasible solution). With two corrections on the master direction by two simple explicit formulas, the algorithm generates a feasible descent direction for the simplified problem and a height-order correction direction which can avoid the Maratos effect without the strict complementarity, then performs a curve search to obtain the next iteration point. Thanks to the new height-order correction technique, under mild conditions without the strict complementarity, the globally and superlinearly convergent properties are obtained. Finally, an efficient implementation of the numerical experiments is reported. [Copyright &y& Elsevier]

Abstract: A novel phasor computation algorithm is presented in this paper. The real and imaginary part filters of this algorithm have identical magnitude frequency characteristic (IMFC) at all the frequencies and orthogonal phase frequency characteristic (PFC) at fundamental frequency. Considering the conditions of the same magnitude frequency characteristic (MFC) and the orthogonal PFC, the two-sample algorithm is derived. Once two-sample orthogonal filters with IMFC are obtained, the algorithm design is just to select proper shapes and lengths of windows, which determine the filtering performance and response-time, respectively. This method could be applied to design filter in any window-length, especially in short-window. Therefore, this class of phasor algorithms is suitable for EHV transmission line protection where a short-window is crucial for fast response and better operation performance. The proposed algorithm has been applied to a series of EHV relay devices by China Xuchang Relay Group. [Copyright &y& Elsevier]

In this paper, DFOM algorithm is presented. We compare DGMRES algorithm with DFOM algorithm by numerical experiment. Error analysis for projection method is also given. [Copyright &y& Elsevier]

Numerically solving the two dimensional open channel flow equations over large spatial domains coupled with long time periods using an explicit finite difference scheme is constrained by the required computational time. To overcome this limitation, in this paper the effect of using a moving boundary algorithm on both the accuracy of the transient solution and on the associated computational savings is investigated. While all the reported studies that relate to solving the two dimensional shallow water open channel flows have used fixed domain boundaries, this work differs from them in that the location of the domain boundaries is a function of the time period. The theory underlying the Eulerian school of thought is used for identifying the coordinates of the domain boundaries. The results indicate that for simulations in which the transient solution is required, the present approach can accelerate the solution with out affecting its accuracy. [Copyright &y& Elsevier]

Abstract: The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations. [Copyright &y& Elsevier]

The paper provides a system theoretic characterisation of the least common multiple (LCM) m(s) of a given set of polynomials P which leads to an efficient numerical procedure for the computation of LCM that avoids root finding and use of greatest common divisor (GCD) procedures. The procedure that is presented also leads to the computation of the associated set of multipliers of P with respect to LCM. The basis of the new characterisation and computational procedure are the controllability properties of a natural realization S(A,b,C) associated with the set P. It is shown, that the coefficients of the LCM are defined by the properties of the controllable subspace of the pair (A,b), which also leads to the characterisation of associated multipliers. An algorithmic procedure that exploits the companion structure of A is formulated and its numerical properties are investigated. The new method provides a robust procedure for the computation of LCM and enables the computation of approximate values, when the original data are innacurate. [Copyright &y& Elsevier]

Most collision detection algorithms are ones of a discrete type which utilize convexity and local coherence to verify the closest points. However, the incremental algorithms have such critical drawbacks like failure to detect high-speed collisions and dependence on the time complexity on the time step size of animation. In this paper, in order to find a new method which can resolve the drawbacks, we are concerned with a more restricted but nontrivial version of the problem: given a fixed infinite plane H and a moving convex polyhedron P, compute their collision time. Our algorithm utilizes the spherical extreme vertex diagram that is the embedding of the dual graph P onto the Gauss sphere. Exploiting the diagram, we are able to efficiently compute the sequence of the extreme vertices vis, i = 1, …, m and find the time interval [ti, ti+1] during which vi is the extreme vertex of P. With the sequences of the consecutive time intervals and extreme vertices, we construct a distance function between P and H. Hence, we can compute their collision time within a given tolerance by applying the interval Newton method to the distance function. Moreover, the total time complexity is independent of the time step size of animation. [Copyright &y& Elsevier]

In this paper we establish several algorithm of discretized parallel chaotic waveform relaxation methods for solving linear ordinary differential systems based on some given models. Under some different assumptions on the coefficient matrix A and its multisplittings we obtain corresponding sufficient conditions for convergence of the algorithms. Also a discussion on convergence speed comparison of synchronous and asynchronous algorithms is given. [Copyright &y& Elsevier]