An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals

In this paper, we present an optimal, exponential space algorithm for generating the reduced Gröbner basis of binomial ideals. We make use of the close relationship between commutative semigroups and pure difference binomial ideals. Based on an optimal algorithm for the uniform word problem in commutative semigroups, we first derive an exponential space algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals. In addition to some applications to finitely presented commutative semigroups, this algorithm is then extended to an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals over Q in general.     

A Convergence Analysis of the Inexact Simplified Jacobi–Davidson Algorithm for Polynomial Eigenvalue Problems

The simplified Jacobi–Davidson (JD) method is a variant of the JD method without subspace acceleration. If the correction equation is solved approximately, the inexact simplified JD method is obtained. In this paper, we present a new convergence analysis of the inexact simplified JD method. The analysis applies to polynomial eigenvalue problems with simple eigenpairs. We first establish a relationship between the solution of the correction equation and the residual of the approximate eigenpair. From this relationship, we find the difference of two adjacent approximate eigenvalues bounded in terms of the residual norm of the approximate eigenpair. Then we prove the convergence of the inexact simplified JD method in terms of the residual norm of the approximate eigenpair. Depending on how accurately we solve the correction equation, the convergence rate of the inexact simplified JD may take several different forms. Numerical experiments confirm the convergence analysis.     

An Algorithm for Timing Verification of Systems Constrained by Min–max Inequalities

To determine the maximum separation between events for nonrepetitive systems with max and linear constraints, there are the “iterative tightening from above” (ITA) approach and the “iterative tightening from below” (ITB) approach. Since such systems can be formulated as systems constrained by min–max inequalities, this paper gives an algorithm named MMIMaxSep for solving min–max inequalities. The algorithm is a generalization and a mathematically elegant reformulation of Yen et al.’s MaxSeparation algorithm which uses the ITB approach. Our numerical experiments indicate that MMIMaxSep is very efficient. Moreover, MMIMaxSep has a unique advantage of being able to directly handle tree-represented min–max functions, and its complexity is closely related to the complexity of computing cycle time of min–max functions.

An Improved Algorithm for Finding the Closest Pair of Points

As early as in 1975, Shamos and Hoey first gave an O（n lg n）-time divide-and-conquer algorithm （Stt algorithm in short） for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to （3n lg n）/2, which is only half that of SH algorithm.     

A Parallel Algorithm for Finding Roots of a Complex Polynomial

A distribution theory of the roots of a polynomial and a parallel algorithm for finding roots of a complex polynomial based on that theory are developed in this paper.With high parallelism,the algorithm is an improvement over the Wilf algorithm^[3].     

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals,and Applications to Commutative Semigroups

It is known that the reduced Gröbner basis of general polynomial ideals can be computed in exponential space. The algorithm, obtained by Kühnle and Mayr, is, however, based on rather complex parallel computations, and, above that, makes extensive use of the parallel computation thesis. In this paper, we exhibit an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals which can be implemented without any complex parallel computations. This result is then applied to derive space optimal decision procedures for the finite enumeration and subword problems for commutative semigroups.     

A New Subdivision Algorithm for the Bernstein Polynomial Approach to Global Optimization

In this paper,an improved algorithm is proposed for unconstrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems.The proposed algorithm is based on the Bernstein polynomial approach.Novel features of the proposed algorithm are that it uses a new rule for the selection of the subdivision point,modified rules for the selection of the subdivision direction,and a new acceleration device to avoid some unnecessary subdivisions.The performance of the proposed algorithm is numerically tested on a collection of 16 test problems.The results of the tests show the proposed algorithm to be superior to the existing Bernstein algorithm in terms of the chosen performance metrics.     

An Efficient Algorithm for the Calculation of NURBS Curves and All Their Derivatives

Through a precise recursion of B-spline bases, this paper presents an efficient algorithm for the calculation of NURBS curves and all their derivatives. The algorithm requires less storage and is proved to be stable.     

On two versions of the Loomis–Sikorski Theorem for algebraic structures

We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra. The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26 SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic and logical systems of soft computing”, and MURST, project “Analisi Reale”.     

An Efficient Optimization Procedure for Tetrahedral Meshes by Chaos Search Algorithm

A simple and efficient local optimization-based procedure for node reposition-ing/smoothing of three-dimensional tetrahedral meshes is presented.The initial tetrahedral mesh is optimized with respect to a specified element shape measure by chaos search algorithm,which is very effective for the optimization problems with only a few design variables.Examples show that the presented smoothing procedure can provide favorable conditions for local transformation approach and the quality of mesh can be significantly improved by the combination of these two procedures with respect to a specified element shape measure.Meanwhile,several commonly used shape measures for tetrahedral element,which are considered to be equivalent in some weak sense over a long period of time,are briefly re-examined in this paper.Preliminary study indicates that using different measures to evaluate the change of element shape will probably lead to inconsistent result for both well shaped and poorly shaped elements.The proposed smoothing approach can be utilized as an appropriate and effective tool for evaluating element shape measures and their influence on mesh optimization process and optimal solution.     

An Algorithm for Determining Minimal Reduced-Coverings of Acyclic Database Schemes

1IntroductionItiswell-knownthatacyclicdatabaseschemeshavesomeverydesirablepr0P-erties-Thesepr0pertie8areappliedwidelyinb0thdesignandmanagement0fdatabases[1'3].Atpresent,therearemanyresultsab0utacyclicdatabaseschemesI1-4'7].Animp0rtantbranchoftheseresultsisthepr0blemofminimalcovers.Veryoften,inbothdesignandmanagementofdatabase,0nlyaset0fpartialrelationorsets0fattributeswithsomespecia.lproperties0fadatabaseschemeareconcerned.Applications0fthesesortsleadtothestudy0fmanyproblemsab0ut..lnummumand…     

An Algorithm for Determining Database Consistency Under the Closed World Assumption

It is well-known that there are circumstances where applying Reiter's closed world assump-tion (CWA) will lead to logical inconsistencies . In this paper, a new characterization of theCWA consistency is pesented and an algorithm is proposed for determining whether a datalase with-out function symbols is consistent with the CWA. The algorithm is shown to be efficient.     

An Algorithm for Determining Database Consistency Under the Closed World Assumption

It is well-known that there are circumstances where applying Reiter‘s closed world assumption(CWA)will lead to logical inconsistencies.In this paper,a new characterization of the CA consistency is pesented and an algorithm is proposed for determining whether a datalase without function symbols is consistent with the CWA.The algorithm is shown to be efficient.     

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ?-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X _ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ?-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ?=?(G) and M _e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ?(G) exactly in time O(? ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ?-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+?) in time O(? ^?2 n ⁵logn).     

An integrated Data Envelopment Analysis–Artificial Neural Network–Rough Set Algorithm for assessment of personnel efficiency

Personnel specifications have greatest impact on total efficiency. They can help us to design work environment and enhance total efficiency. Determination of critical personnel attributes is a useful procedure to overcome complication associated with multiple inputs and outputs. The proposed algorithm assesses the impact of personnel efficiency attributes on total efficiency through Data Envelopment Analysis (DEA), Artificial Neural Network (ANN) and Rough Set Theory (RST). DEA has two roles in the proposed integrated algorithm of this study. It provides data ANN and finally it selects the best reduct through ANN result. Reduct is described as a minimum subset of attributes, completely discriminating all objects in a data set. The reduct selection is achieved by RST. ANN has two roles in the integrated algorithm. ANN results are basis for selecting the best reduct and it is also used for forecasting total efficiency. The proposed integrated approach is applied to an actual banking system and its superiorities and advantages are discussed.     

An Interactive Learning Algorithm for Acquisition of Concepts Represented as CFL

In this paper,an interactive learning algorithm of context-frmm language is presented.This algorithm is designed especially for system SAQ,which is a system for formal secification acquisition and verification.As the kernel of concept acquisition subsystem(SAQ/CL)of SAQ,the algorithm has been implemented on SUN SPARC workstation.The grammar to be obtained can represent sentence structure naturally.     

An Adaptive Algorithm for the Time Dependent Transport Equation with Anisotropic Finite Elements and the Crank–Nicolson Scheme

Anisotropic finite elements and the Crank–Nicolson scheme are considered to solve the time dependent transport equation. Anisotropic a priori and a posteriori error estimates are derived. The sharpness of the error indicator is studied on non-adapted meshes and time steps. An adaptive algorithm in space and time is then designed to control the error at final time. Numerical results show the accuracy of the method.     

Generalization of the Firm’s Profit Maximization Problem: An Algorithm for the Analytical and Nonsmooth Solution

In this paper we present a generalization of the classic Firm’s profit maximization problem, using the linear model for the production function, considering a non constant price and maximum constraints for the inputs. We formulate the problem by previously calculating the analytical minimum cost function. This minimum cost function will be calculated for each production level via the infimal convolution of quadratic functions and the result will be a piecewise quadratic function. To solve this family of optimization problems, we present an algorithm of quasi-linear complexity. Moreover, the resulting cost function in certain cases is not $C^{1}$ and the profit maximization problem will be solved within the framework of nonsmooth analysis. Finally, we present a numerical example.     

Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds.