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: In this paper an attempt is made to extend some standard results in set theory on the basis of soft set relations. Antisymmetric relation and transitive closure of a soft set relation are introduced and an analogue of Warshall’s algorithm is proposed for calculating the transitive closure of a soft set relation. Ordering on a soft set is defined and some set theoretical results based on this are proved. [Copyright &y& Elsevier]

Abstract: This paper proposes improved delay-dependent conditions for asymptotic stability of linear systems with time-varying delays. The proposed method employs a suitable Lyapunov–Krasovskii’s functional for new augmented system. Based on Lyapunov method, delay-dependent stability criteria for the systems are established in terms of linear matrix inequalities (LMIs) which can be easily solved by various optimization algorithms. Three numerical examples are included to show that the proposed method is effective and can provide less conservative results. [Copyright &y& Elsevier]

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: According to the hierarchical identification principle, a hierarchical gradient based iterative estimation algorithm is derived for multivariable output error moving average systems (i.e., multivariable OEMA-like models) which is different from multivariable CARMA-like models. As there exist unmeasurable noise-free outputs and unknown noise terms in the information vector/matrix of the corresponding identification model, this paper is, by means of the auxiliary model identification idea, to replace the unmeasurable variables in the information vector/matrix with the estimated residuals and the outputs of the auxiliary model. A numerical example is provided. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, an inversion algorithm for a banded matrix is presented. The twisted decompositions of a banded matrix are given first; then the inverse of the matrix is obtained, one column at time. The method is about two times faster than the standard method based on the decomposition, as is shown with the analysis of computing complexity and the numerical experiments. [Copyright &y& Elsevier]

Abstract: In this work we construct three novel families of approximating subdivision schemes that generate piecewise exponential polynomials and we show how to convert these into interpolating schemes of great interest in curve design for their ability to reproduce important analytical shapes and to provide highly smooth limit curves with a controllable tension. In particular, throughout this paper we will focus on the derivation of 6-point interpolating schemes that turn out to be unique in combining vital ingredients like -continuity, simplicity of definition, ease of implementation, user independency, tension control and ability to reproduce salient trigonometric and transcendental curves. [Copyright &y& Elsevier]

Abstract: In this paper, by using the theories and methods of mathematical analysis and computer algebra, a reliable algorithm of finite difference method for solving singular perturbation problems was established, a new matlab procedure ehssp was implemented, too. Several linear and non-linear problems are presented to illustrate the implementation of the program. [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, for the nonlinear diffusion model of image denoising and segmentation, we present two high-order explicit algorithms and a semi-implicit algorithm using algebraic multi-grid method. The unconditional stability of the semi-implicit approximation is given. The numerical results of the above three algorithms are demonstrated with comparison to general explicit algorithm in [Y. Chen, B.C. Vemuri, L. Wang, Image denoising and segmentation via nonlinear diffusion, Comput. Math. Appl. 39 (2000) 131–149] for real noised images. The numerical results show that the implicit algorithm is quicker and sharper than all explicit algorithms. [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: A modified Rayleigh conjecture (MRC) in scattering theory was proposed and justified by the author [A.G. Ramm, Modified Rayleigh conjecture and applications, J. Phys. A 35 (2002) L357–L361]. The MRC allows one to develop efficient numerical algorithms for solving boundary-value problems. It gives an error estimate for solutions. In this paper the MRC is formulated and proved for static problems. [Copyright &y& Elsevier]

Abstract: One of the main problems dealing with iterative methods for solving polynomial systemsis the initialization of the iteration. This paper provides an algorithm to initialize the search of solutions of polynomial systems. [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: The paper presents an efficient algorithm to solve a one-dimensional as well as n-dimensional circulant convolution system. The proposed algorithm does not introduce computational errors into the solution. Its derivation is based on polynomial algebra operations that allow to express the operation of deconvolution as a sequence of convolutions of both response and output signals. [Copyright &y& Elsevier]

Abstract: This paper proves the convergence of some generalized Schwarz algorithms for solvingthe obstacle problems with a T-monotone operator. Numerical results show that the generalized Schwarz algorithms converge faster than the classical Schwarz algorithms. [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]

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 give a numerically reliable algorithm to compute the zeros of a periodic descriptor system. The algorithm is a variant of the staircase algorithm applied to the system pencil of an equivalent lifted time-invariant state-space system and extracts a low-order pencil which contains the zeros (both finite and infinite) as well as the Kronecker structure of the periodic descriptor system. The proposed algorithm is efficient in terms of complexity by exploiting the structure of the pencil and is exclusively based on orthogonal transformations, which ensures some form of numerical stability. [Copyright &y& Elsevier]

This paper presents some new techniques in designing finite-difference domain decomposition algorithm for the heat equation. The basic procedure is to define the finite-difference schemes at the interface grid points with smaller time step Δt = SHAPE="SOL" ALIGN="C" STYLE="S">Δtm (m is a positive integer) by Saul''yev asymmetric schemes. The algorithm can increase the stability bounds of the classical explicit method by 2m times, and the prior error estimates for the numerical solutions are obtained for some algorithms when m = 2 or m = 3. Numerical experiments on stability and accuracy are also presented. [Copyright &y& Elsevier]