Designing Optimal Algorithms for Solving Banded Triangular Systems on Rings

Parallel complexity results for designing banded triangular solvers are provided. In particular, several lower bounds based on data layout and communication along a ring are derived based on solving such systems using substitution. Lastly, a near-optimal solver for a ring is discussed and provided.     

Global Optimization Requires Global Information

There are many global optimization algorithms which do not use global information. We broaden previous results, showing limitations on such algorithms, even if allowed to run forever. We show that deterministic algorithms must sample a dense set to find the global optimum value and can never be guaranteed to converge only to global optimizers. Further, analogous results show that introducing a stochastic element does not overcome these limitations. An example is simulated annealing in practice. Our results show that there are functions for which the probability of success is arbitrarily small.     

Real-Code Genetic Algorithm for Ground State Energies of Hydrogenic Donors in GaAs-(Ga,Al)As Quantum Dots

We present a global optimization method, called the real-code genetic algorithm (RGA), to the ground state energies. The proposed method does not require partial derivatives with respect to each variational parameter or solving an eigenequation, so the present method overcomes the major difficulties of the variational method. RGAs also do not require coding and encoding procedures, so the computation time and complexity are reduced. The ground state energies of hydrogenic donors in GaAs-(Ga,Al)As quantum dots have been calculated for a range of the radius of the quantum dot radii of practical interest. They are compared with those obtained by the variational method. The results obtained demonstrate the proposed method is simple, accurate, and easy implement.     

PARALLEL ALGORITHMS OF ONE-LEG METHOD AND ITERATED DEFECT CORRECTION METHODS

The parallel algorithms of iterated defect correction methods (PIDeCM's) are constructed, which are of efficiency and high order B-convergence for general nonlinear stiff systems in ODE'S. As the basis of constructing and discussing PIDeCM's. a class of parallel one-leg methods is also investigated, which are of particular efficiency for linear systems.     

THE SUBDIVISION ALGORITHM FOR GENERATING CURVES AND ITS PROPERTIES

ＴＨＥＳＵＢＤＩＶＩＳＩＯＮＡＬＧＯＲＩＴＨＭＦＯＲＧＥＮＥＲＡＴＩＮＧＣＵＲＶＥＳＡＮＤＩＴＳＰＲＯＰＥＲＴＩＥＳＷＵＺＯＮＧＭＩＮ；ＹＥＱＩＮＧＡＮＤＬＩＵＪＩＡＮＰＩＮＡｂｓｔｒａｃｔ：ＩｎｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆＣＡＤ／ＣＡＭ，ｔｈｅ...     

Tree decompositions of graphs: Saving memory in dynamic programming

We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced “anchor technique” is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.     

资源公平分配的遗传算法研究

文章对决策优化的经典问题席位公平分配进行了研究，提出应用遗传算法对该模型进行求解。两例资源公平分配决策实例研究表明，遗传算法优化结果较其它方法都更合理。     

On <Emphasis Type="Italic">τ</Emphasis>-adic representations of integers

Elliptic curve cryptosystems (ECCs) have become increasingly popular due to their efficiency and the small size of the keys they use. Particularly, the anomalous curves introduced by Koblitz allow a complex representation of the keys, denoted τNAF, that make the computations over these curves more efficient. In this article, we propose an efficient method for randomizing a τNAF to produce different equivalent representations of the same key to the same complex base τ. We prove that the average Hamming density of the resulting representations is 0.5. We identify the pattern of the τNAFs yielding the maximum number of representations and the formula governing this number. We also present deterministic methods to compute the average and the exact number of possible representations of a τNAF.      

A new parallel chasing algorithm for transforming arrowhead matrices to tridiagonal form

Rutishauser, Gragg and Harrod and finally H.Y. Zha used the same class of chasing algorithms for transforming arrowhead matrices to tridiagonal form. Using a graphical theoretical approach, we propose a new chasing algorithm. Although this algorithm has the same sequential computational complexity and backward error properties as the old algorithms, it is better suited for a pipelined approach. The parallel algorithm for this new chasing method is described, with performance results on the Paragon and nCUBE. Comparison results between the old and the new algorithms are also presented.

     

Long-Step Path-Following Algorithm for Convex Quadratic Programming Problems in a Hilbert Space

We develop an interior-point technique for solving quadratic programming problems in a Hilbert space. As an example, we consider an application of these results to the linear-quadratic control problem with linear inequality constraints. It is shown that the Newton step in this situation is basically reduced to solving the standard linear-quadratic control problem.