The complexity of achievement and maintenance problems in agent-based systems

We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The different problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete (when they are not trivial). We also consider alternative achievement and maintenance agent design problems by allowing longer runs in environments (that is, our environments are bounded but the bounds are more liberal than was the case previously). Again, we obtain a complete classification but so that the different problems are DEXPTIME-complete, NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACE-complete (when they are not trivial).     

Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.     

Complexity of graph self-assembly in accretive systems and self-destructible systems

Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. It is ubiquitous in biological constructions at the cellular and molecular scale and has also been identified by nanoscientists as a fundamental method for building nano-scale structures. Recent years have seen convergent interest and efforts in studying self-assembly from mathematicians, computer scientists, physicists, chemists, and biologists. However most complexity theoretical studies of self-assembly utilize mathematical models with two limitations: (1) only attraction, while no repulsion, is studied; (2) only assembled structures of two dimensional square grids are studied. In this paper, we study the complexity of the assemblies resulting from the cooperative effect of repulsion and attraction in a more general setting of graphs. This allows for the study of a more general class of self-assembled structures than the previous tiling model. We define two novel assembly models, namely the accretive graph assembly model and the self-destructible graph assembly model, and identify a fundamental problem in them: the sequential construction of a given graph. We refer to it as the Accretive Graph Assembly Problem (AGAP) and the Self-Destructible Graph Assembly Problem (DGAP), in the respective models. Our main results are: (i) AGAP is NP-complete even if the maximum degree of the graph is restricted to 4 or the graph is restricted to be planar with maximum degree 5; (ii) counting the number of sequential assembly orderings that result in a target graph (#AGAP) is #P-complete; and (iii) DGAP is PSPACE-complete even if the maximum degree of the graph is restricted to 6 (this is the first PSPACE-complete result in self-assembly). We also extend the accretive graph assembly model to a stochastic model, and prove that determining the probability of a given assembly in this model is #P-complete.     

Heuristic computation of the rovibrational G matrix in optimized molecule-fixed axes. Gmat 2.1

Gmat 2.1 is a program able to compute the rovibrational G matrix in different molecule-fixed axes extending the capabilities of Gmat 1.0. The present version is able to select optimal molecule-fixed axes minimizing the pure rotational kinetic elements, the rovibrational kinetic elements or both simultaneously. To such an end, it uses a hybrid minimization approach. Thus, it combines a global search heuristic based in simulated annealing with a gradient-free local minimization. As the previous version, the program handles the structural results of potential energy hypersurface mappings computed in computer clusters or computational Grid environments. However, since now more general molecule-fixed axes can be defined, a procedure is implemented to ensure the same minimum of the cost function is used in all the molecular structures. In addition, an algorithm for the unambiguous definition of the molecule-fixed axes orientation is used.

Program summary

Program title: Gmat 2.1Catalogue identifier: AECZ_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AECZ_v2_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 52 555No. of bytes in distributed program, including test data, etc.: 932 366Distribution format: tar.gzProgramming language: Standard ANSI C++Computer: AllOperating system: Linux, WindowsClassification: 16.2Catalogue identifier of previous version: AECZ_v1_0Journal reference of previous version: Comput. Phys. Comm. 180 (2009) 1183Does the new version supersede the previous version?: YesNature of problem: When building molecular rovibrational Hamiltonians, the kinetic terms depend on the molecule-fixed axes orientation. Thus, an appropriate orientation can significantly simplify the treatment of pure rotation and rovibrational coupling. The kinetic terms are collected in the rovibrational G matrix. Thus, selection of an appropriate molecule-fixed reference frame is equivalent to localize the axes that minimize specific G matrix elements. From this standpoint, three different kinds of molecule-fixed axes are of interest: first, axes minimizing pure rotational elements of the G matrix; second, axes minimizing all the rovibrational G matrix elements; third, axes minimizing simultaneously pure rotational + rovibrational coupling elements.Solution method: In order to carry out the optimal selection of molecule-fixed axes, we add a hybrid method of minimization to the capabilities included in the first version of the program [1]. Thus, we minimize specific elements of the rovibrational G matrix. To such an end, we apply a heuristic global optimization strategy, simulated annealing [2], followed by a Powell's local minimization [3]. We also include a procedure to ensure that the same minimum is used when several molecular configurations are considered. In addition, an unambiguous molecule-fixed axes ordering is implemented.Reasons for new version: The previous version of the program, Gmat 1.0, works in principal axes of inertia. Although this axes system is adequate for pure vibrational Hamiltonians, it is not always optimal for the construction of general rovibrational Hamiltonians. However, implementing the methods presented here, we can obtain molecule-fixed axes minimizing pure rotational or/and rovibrational interactions in the G matrix. In this form, we can derive the simplest analytical form of the rovibrational Hamiltonian.Summary of revisions: Some new methods have been introduced:

1.

A method to build the molecule-fixed axes rotation matrix from the Euler angles.

2.

Methods for rotating nuclear coordinates and their derivatives using the rotation matrix.

3.

A method for applying simulated annealing to the search of the global minimum of a cost function formed by rotational or rovibrational G matrix elements.

4.

A method implementing Powell.

Running time: The sample tests take a few seconds to execute.References:

[1]

M.E. Castro, A. Niño, C. Muñoz-Caro, Comput. Phys. Comm. 180 (2009) 1183.

[2]

S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, Science 220 (4598) (1983) 671.

[3]

W.H. Press, B.P. Flannery, S.A. Teukolsky, W.T. Vetterling, Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, Cambridge, 2007.

     

An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks

The connected dominating set (CDS) is widely used as a virtual backbone in mobile ad hoc networks. Although many distributed algorithms for constructing the CDS have been proposed, nearly all of them require two or more separated phases, which may cause problems such as long delay in the later phases when the network size is large. This paper proposes a Distributed Single-Phase algorithm for constructing a connected dominating set, DSP-CDS, in ad hoc networks. The DSP-CDS is an asynchronous distributed algorithm and converges quickly in a single phase. Each node uses one-hop neighborhood information and makes a local decision on whether to join the dominating set. Each node bases its decision on a key variable, strength, which guarantees that the dominating set is connected when the algorithm converges. The rules for computing strength can be changed to accommodate different application needs. The DSP-CDS adapts well to dynamic network topologies, upon which the algorithm makes only necessary local updates to maintain the CDS of the network. The performance of the DSP-CDS can be tuned by adjusting two main parameters. Extensive simulations have demonstrated that those parameters can affect the CDS size, the CDS diameter, and number of rounds for the algorithm to converge. Comparisons with other multiple-phase CDS algorithms have shown that the DSP-CDS converges fast and generates a CDS of comparable size.     

FINE: A Fully Informed aNd Efficient communication-induced checkpointing protocol for distributed systems

Communication-Induced Checkpointing (CIC) protocols are classified into two categories in the literature: Index-based and Model-based. In this paper, we discuss two data structures being used in these two kinds of CIC protocols, and their different roles in helping the checkpointing algorithms to enforce Z-cycle Free (ZCF) property. Then, we present our Fully Informed aNd Efficient (FINE) communication-induced checkpointing algorithm, which not only has less checkpointing overhead than the well-known Fully Informed (FI) CIC protocol proposed by Helary et al. but also has less message overhead. Performance evaluation indicates that our protocol performs better than many of the other existing CIC protocols.     

CADNA: a library for estimating round-off error propagation

The CADNA library enables one to estimate round-off error propagation using a probabilistic approach. With CADNA the numerical quality of any simulation program can be controlled. Furthermore by detecting all the instabilities which may occur at run time, a numerical debugging of the user code can be performed. CADNA provides new numerical types on which round-off errors can be estimated. Slight modifications are required to control a code with CADNA, mainly changes in variable declarations, input and output. This paper describes the features of the CADNA library and shows how to interpret the information it provides concerning round-off error propagation in a code.

Program summary

Program title:CADNACatalogue identifier:AEAT_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEAT_v1_0.htmlProgram obtainable from:CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions:Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.:53 420No. of bytes in distributed program, including test data, etc.:566 495Distribution format:tar.gzProgramming language:FortranComputer:PC running LINUX with an i686 or an ia64 processor, UNIX workstations including SUN, IBMOperating system:LINUX, UNIXClassification:4.14, 6.5, 20Nature of problem:A simulation program which uses floating-point arithmetic generates round-off errors, due to the rounding performed at each assignment and at each arithmetic operation. Round-off error propagation may invalidate the result of a program. The CADNA library enables one to estimate round-off error propagation in any simulation program and to detect all numerical instabilities that may occur at run time.Solution method:The CADNA library [1] implements Discrete Stochastic Arithmetic [2-4] which is based on a probabilistic model of round-off errors. The program is run several times with a random rounding mode generating different results each time. From this set of results, CADNA estimates the number of exact significant digits in the result that would have been computed with standard floating-point arithmetic.Restrictions:CADNA requires a Fortran 90 (or newer) compiler. In the program to be linked with the CADNA library, round-off errors on complex variables cannot be estimated. Furthermore array functions such as product or sum must not be used. Only the arithmetic operators and the abs, min, max and sqrt functions can be used for arrays.Running time:The version of a code which uses CADNA runs at least three times slower than its floating-point version. This cost depends on the computer architecture and can be higher if the detection of numerical instabilities is enabled. In this case, the cost may be related to the number of instabilities detected.References:

[1]

The CADNA library, URL address: http://www.lip6.fr/cadna.

[2]

J.-M. Chesneaux, L'arithmétique Stochastique et le Logiciel CADNA, Habilitation á diriger des recherches, Université Pierre et Marie Curie, Paris, 1995.

[3]

J. Vignes, A stochastic arithmetic for reliable scientific computation, Math. Comput. Simulation 35 (1993) 233-261.

[4]

J. Vignes, Discrete stochastic arithmetic for validating results of numerical software, Numer. Algorithms 37 (2004) 377-390.

     

An adaptive overlay network inspired by social behaviour

Nature is a great source of inspiration for scientists, because natural systems seem to be able to find the best way to solve a given problem by using simple and robust mechanisms. Studying complex natural systems, scientists usually find that simple local dynamics lead to sophisticated macroscopic structures and behaviour. It seems that some kind of local interaction rules naturally allow the system to auto-organize itself as an efficient and robust structure, which can easily solve different tasks. Examples of such complex systems are social networks, where a small set of basic interaction rules leads to a relatively robust and efficient communication structure. In this paper, we present PROSA, a semantic peer-to-peer (P2P) overlay network inspired by social dynamics. The way queries are forwarded and links among peers are established in PROSA resemble the way people ask other people for collaboration, help or information. Behaving as a social network of peers, PROSA naturally evolves to a small world, where all peers can be reached in a fast and efficient way. The underlying algorithm used for query forwarding, based only on local choices, is both reliable and effective: peers sharing similar resources are eventually connected with each other, allowing queries to be successfully answered in a really small amount of time. The resulting emergent structure can guarantee fast responses and good query recall.     

Four-arc approximation to ellipses: The best in general

So far, the four-arc approximations to an ellipse E are made under the condition that the major and minor axes keep strictly unchanged. In general, however, this condition is unnecessary. Then the fitting can be further improved. Considering a representative quadrant of E, we first draw two auxiliary circular arcs tangent to E at the axes but having a gap ε at their boundary, such that the small arc S lies outside the large arc L. Meanwhile the extreme errors of S and L w.r.t. E are ε and −ε respectively. Giving the radii of S and L a decrement −ε/2 and an increment ε/2 brings them to join smoothly. Thus, reducing the overall error to minimum, an analytic solution in implicit form is derived.     

Model-Driven Development for scientific computing. Computations of RHEED intensities for a disordered surface. Part II

Modelling, simulation, and visualisation together create the third branch of human knowledge on equal footing with theory and experiment. Model-Driven Development (MDD) has been proposed as a means to support the software development process through the use of a model-centric approach. The objective of this paper is to address the design of an architecture for scientific application that may execute as multithreaded computations, as well as implementations of the related shared data structures.

New version program summary

Program title: Growth09Catalogue identifier: ADVL_v3_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADVL_v3_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 30 940No. of bytes in distributed program, including test data, etc.: 3 119 488Distribution format: tar.gzProgramming language: Embarcadero DelphiComputer: Intel Core Duo-based PCOperating system: Windows XP, Vista, 7RAM: more than 1 GBClassification: 4.3, 7.2, 6.2, 8, 14Catalogue identifier of previous version: ADVL_v2_1Journal reference of previous version: Comput. Phys. Comm. 180 (2009) 1219Subprograms used:

Cat Id	Title	Reference
ADUY_v4_0	RHEED1DProcess	CPC 999 (9999) 9999

Full-size table

     

A dual K-Na selective Prussian blue nanotubes sensor

A strategy for dual sensing of Na⁺ and K⁺ ions using Prussian blue nanotubes via selective inter/deintercalation of K⁺ ion and competitive inhibition by Na⁺ ion, is reported. The analytical signal is derived from the cyclic voltammetry cathodic peak position E_pc of Prussian blue nanotubes. Na⁺ and K⁺ levels in a sample solution can be determined conveniently using one Prussian blue nanotubes sensor. In addition, this versatile method can be applied for the analysis of single type of either Na⁺ or K⁺ ions. The dual-ion sensor response towards Na⁺ and K⁺ can be described using a model based on the competitive inhibition effects of Na⁺ on K⁺ inter/deintercalation in Prussian blue nanotubes. Successful application of the Prussian blue nanotubes sensor for Na⁺ and K⁺ determination is demonstrated in artificial saliva.     

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +ε)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +ε)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +ε)-approximation algorithm for an MWCDS.     

Efficient processing of k-hop reachability queries

We study the problem of answering k -hop reachability queries in a directed graph, i.e., whether there exists a directed path of length $k$ , from a source query vertex to a target query vertex in the input graph. The problem of $k$ -hop reachability is a general problem of the classic reachability (where $k=\infty $ ). Existing indexes for processing classic reachability queries, as well as for processing shortest path distance queries, are not applicable or not efficient for processing $k$ -hop reachability queries. We propose an efficient index for processing $k$ -hop reachability queries. Our experimental results on a wide range of real datasets show that our method is efficient and scalable in terms of both index construction and query processing.     

From Holant to #CSP and Back: Dichotomy for Holant c Problems

We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions that take boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain ?. We prove three complexity dichotomy theorems, leading to a general theorem for Holant ^c problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on G=(V,E) over a set of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to? ,?of $$\sum_{\sigma: E \rightarrow \{0,1\}}\prod_{v\in V} f_v(\sigma \vert _{E(v)}),$$ where (0, 1 are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy can be only naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on Boolean complex weighted #CSP.     

POTHMF: A program for computing potential curves and matrix elements of the coupled adiabatic radial equations for a hydrogen-like atom in a homogeneous magnetic field

A FORTRAN 77 program is presented which calculates with the relative machine precision potential curves and matrix elements of the coupled adiabatic radial equations for a hydrogen-like atom in a homogeneous magnetic field. The potential curves are eigenvalues corresponding to the angular oblate spheroidal functions that compose adiabatic basis which depends on the radial variable as a parameter. The matrix elements of radial coupling are integrals in angular variables of the following two types: product of angular functions and the first derivative of angular functions in parameter, and product of the first derivatives of angular functions in parameter, respectively. The program calculates also the angular part of the dipole transition matrix elements (in the length form) expressed as integrals in angular variables involving product of a dipole operator and angular functions. Moreover, the program calculates asymptotic regular and irregular matrix solutions of the coupled adiabatic radial equations at the end of interval in radial variable needed for solving a multi-channel scattering problem by the generalized R-matrix method. Potential curves and radial matrix elements computed by the POTHMF program can be used for solving the bound state and multi-channel scattering problems. As a test desk, the program is applied to the calculation of the energy values, a short-range reaction matrix and corresponding wave functions with the help of the KANTBP program. Benchmark calculations for the known photoionization cross-sections are presented.

Program summary

Program title:POTHMFCatalogue identifier:AEAA_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEAA_v1_0.htmlProgram obtainable from:CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions:Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.:8123No. of bytes in distributed program, including test data, etc.:131 396Distribution format:tar.gzProgramming language:FORTRAN 77Computer:Intel Xeon EM64T, Alpha 21264A, AMD Athlon MP, Pentium IV Xeon, Opteron 248, Intel Pentium IVOperating system:OC Linux, Unix AIX 5.3, SunOS 5.8, Solaris, Windows XPRAM:Depends on

1.

the number of radial differential equations;

2.

the number and order of finite elements;

3.

the number of radial points.

Test run requires 4 MBClassification:2.5External routines:POTHMF uses some Lapack routines, copies of which are included in the distribution (see README file for details).Nature of problem:In the multi-channel adiabatic approach the Schrödinger equation for a hydrogen-like atom in a homogeneous magnetic field of strength γ (γ=B/B₀, B₀≅2.35×¹⁰⁵ T is a dimensionless parameter which determines the field strength B) is reduced by separating the radial coordinate, r, from the angular variables, (θ,φ), and using a basis of the angular oblate spheroidal functions [3] to a system of second-order ordinary differential equations which contain first-derivative coupling terms [4]. The purpose of this program is to calculate potential curves and matrix elements of radial coupling needed for calculating the low-lying bound and scattering states of hydrogen-like atoms in a homogeneous magnetic field of strength 0<γ?1000 within the adiabatic approach [5]. The program evaluates also asymptotic regular and irregular matrix radial solutions of the multi-channel scattering problem needed to extract from the R-matrix a required symmetric shortrange open-channel reaction matrix K [6] independent from matching point [7]. In addition, the program computes the dipole transition matrix elements in the length form between the basis functions that are needed for calculating the dipole transitions between the low-lying bound and scattering states and photoionization cross sections [8].Solution method:The angular oblate spheroidal eigenvalue problem depending on the radial variable is solved using a series expansion in the Legendre polynomials [3]. The resulting tridiagonal symmetric algebraic eigenvalue problem for the evaluation of selected eigenvalues, i.e. the potential curves, is solved by the LDL^T factorization using the DSTEVR program [2]. Derivatives of the eigenfunctions with respect to the radial variable which are contained in matrix elements of the coupled radial equations are obtained by solving the inhomogeneous algebraic equations. The corresponding algebraic problem is solved by using the LDL^T factorization with the help of the DPTTRS program [2]. Asymptotics of the matrix elements at large values of radial variable are computed using a series expansion in the associated Laguerre polynomials [9]. The corresponding matching points between the numeric and asymptotic solutions are found automatically. These asymptotics are used for the evaluation of the asymptotic regular and irregular matrix radial solutions of the multi-channel scattering problem [7]. As a test desk, the program is applied to the calculation of the energy values of the ground and excited bound states and reaction matrix of multi-channel scattering problem for a hydrogen atom in a homogeneous magnetic field using the KANTBP program [10].Restrictions:The computer memory requirements depend on:

1.

the number of radial differential equations;

2.

the number and order of finite elements;

3.

the total number of radial points.

Restrictions due to dimension sizes can be changed by resetting a small number of PARAMETER statements before recompiling (see Introduction and listing for details).Running time:The running time depends critically upon:

1.

the number of radial differential equations;

2.

the number and order of finite elements;

3.

the total number of radial points on interval [rmin,rmax].

The test run which accompanies this paper took 7 s required for calculating of potential curves, radial matrix elements, and dipole transition matrix elements on a finite-element grid on interval [rmin=0, rmax=100] used for solving discrete and continuous spectrum problems and obtaining asymptotic regular and irregular matrix radial solutions at rmax=100 for continuous spectrum problem on the Intel Pentium IV 2.4 GHz. The number of radial differential equations was equal to 6. The accompanying test run using the KANTBP program took 2 s for solving discrete and continuous spectrum problems using the above calculated potential curves, matrix elements and asymptotic regular and irregular matrix radial solutions. Note, that in the accompanied benchmark calculations of the photoionization cross-sections from the bound states of a hydrogen atom in a homogeneous magnetic field to continuum we have used interval [rmin=0, rmax=1000] for continuous spectrum problem. The total number of radial differential equations was varied from 10 to 18.References:

[1]

W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery, Numerical Recipes: The Art of Scientific Computing, Cambridge University Press, Cambridge, 1986.

[2]

http://www.netlib.org/lapack/.

[3]

M. Abramovits, I.A. Stegun, Handbook of Mathematical Functions, Dover, New York, 1965.

[4]

U. Fano, Colloq. Int. C.N.R.S. 273 (1977) 127; A.F. Starace, G.L. Webster, Phys. Rev. A 19 (1979) 1629-1640; C.V. Clark, K.T. Lu, A.F. Starace, in: H.G. Beyer, H. Kleinpoppen (Eds.), Progress in Atomic Spectroscopy, Part C, Plenum, New York, 1984, pp. 247-320; U. Fano, A.R.P. Rau, Atomic Collisions and Spectra, Academic Press, Florida, 1986.

[5]

M.G. Dimova, M.S. Kaschiev, S.I. Vinitsky, J. Phys. B 38 (2005) 2337-2352; O. Chuluunbaatar, A.A. Gusev, V.L. Derbov, M.S. Kaschiev, V.V. Serov, T.V. Tupikova, S.I. Vinitsky, Proc. SPIE 6537 (2007) 653706-1-18.

[6]

M.J. Seaton, Rep. Prog. Phys. 46 (1983) 167-257.

[7]

M. Gailitis, J. Phys. B 9 (1976) 843-854; J. Macek, Phys. Rev. A 30 (1984) 1277-1278; S.I. Vinitsky, V.P. Gerdt, A.A. Gusev, M.S. Kaschiev, V.A. Rostovtsev, V.N. Samoylov, T.V. Tupikova, O. Chuluunbaatar, Programming and Computer Software 33 (2007) 105-116.

[8]

H. Friedrich, Theoretical Atomic Physics, Springer, New York, 1991.

[9]

R.J. Damburg, R.Kh. Propin, J. Phys. B 1 (1968) 681-691; J.D. Power, Phil. Trans. Roy. Soc. London A 274 (1973) 663-702.

[10]

O. Chuluunbaatar, A.A. Gusev, A.G. Abrashkevich, A. Amaya-Tapia, M.S. Kaschiev, S.Y. Larsen, S.I. Vinitsky, Comput. Phys. Comm. 177 (2007) 649-675.

     

Performance evaluation for a transportation system in stochastic case

In a single-commodity multistate flow network, the arc capacity is stochastic and thus the system capacity (i.e. the maximum flow from the source to the sink) is not a fixed number. This paper constructs a multicommodity multistate flow network with weighted capacity allocation to model a transportation system. Each arc with cost attribute has several possible capacities. The capacity weight, the consumed amount of arc capacity by per commodity, varies with the arcs and types of commodity. We define the system capacity as a demand vector d if the system fulfills at most d. The addressed problem in this work is to measure the service quality of a transportation system. We propose a performance index, the probability that the upper bound of the system capacity equals a demand vector d subject to the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MC that are the maximal capacity vectors meeting exactly the demand d under the budget B. The proposed performance index can be subsequently evaluated in terms of such (d,B)-MC.     

Orthogonal incremental extreme learning machine for regression and multiclass classification

Single-hidden-layer feedforward networks with randomly generated additive or radial basis function hidden nodes have been theoretically proved that they can approximate any continuous function. Meanwhile, an incremental algorithm referred to as incremental extreme learning machine (I-ELM) was proposed which outperforms many popular learning algorithms. However, I-ELM may produce redundant nodes which increase the network architecture complexity and reduce the convergence rate of I-ELM. Moreover, the output weight vector obtained by I-ELM is not the least squares solution of equation Hβ = T. In order to settle these problems, this paper proposes an orthogonal incremental extreme learning machine (OI-ELM) and gives the rigorous proofs in theory. OI-ELM avoids redundant nodes and obtains the least squares solution of equation Hβ = T through incorporating the Gram–Schmidt orthogonalization method into I-ELM. Simulation results on nonlinear dynamic system identification and some benchmark real-world problems verify that OI-ELM learns much faster and obtains much more compact neural networks than ELM, I-ELM, convex I-ELM and enhanced I-ELM while keeping competitive performance.     

A constrained optimization approach for an adaptive generalized subspace tracking algorithm

In this paper, we present an orthonormal version of the generalized signal subspace tracking. It is based on an interpretation of the generalized signal subspace as the solution of a constrained minimization task. This algorithm, referred to as the CGST algorithm, guarantees the C_x-orthonormality of the estimated generalized signal subspace basis at each iteration which C_x denotes the correlation matrix of the sequence x(t). An efficient implementation of the proposed algorithm enhances applicability of it in real time applications.