Matched filters for coalescing binaries detection on massively parallel computers

In this paper we discuss some computational problems associated to matched filtering of experimental signals from gravitational wave interferometric detectors in a parallel-processing environment. We then specialize our discussion to the use of the APEmille and apeNEXT processors for this task. Finally, we accurately estimate the performance of an APEmille system on a computational load appropriate for the LIGO and VIRGO experiments, and extrapolate our results to apeNEXT.     

A novel numerical approach to heterojunction bipolar transistors circuit simulation

In this paper we present a novel computational method for calculating the heterojunction bipolar transistor (HBT) physical characteristics in the time domain. To calculate the HBT high frequency properties, the Gummel-Poon equivalent circuit model is applied to replace the HBT in the circuit and a set of governing ordinary differential equations (ODEs) is formulated. We directly decouple the system ODEs and solve each decoupled ODE with the monotone iterative method in the time domain. This solution methodology proposed here has been applied to semiconductor device simulation by us earlier, and we find this method for the HBT simulation has good accuracy and converges globally. Compared with the HSPICE circuit simulator results, our results present the accuracy, efficiency, and robustness of the method.     

Sampling using a ‘bank’ of clues

An easy-to-implement form of the Metropolis Algorithm is described which, unlike most standard techniques, is well suited to sampling from multi-modal distributions on spaces with moderate numbers of dimensions (order ten) in environments typical of investigations into current constraints on Beyond-the-Standard-Model physics. The sampling technique makes use of pre-existing information (which can safely be of low or uncertain quality) relating to the distribution from which it is desired to sample. This information should come in the form of a “bank” or “cache” of parameter space points of which at least some may be expected to be near regions of interest in the desired distribution. In practical circumstances such “banks of clues” are easy to assemble from earlier work, aborted runs, discarded burn-in samples from failed sampling attempts, or from prior scouting investigations. The technique equilibrates between disconnected parts of the distribution without user input. The algorithm is not lead astray by “bad” clues, but there is no free lunch: performance gains will only be seen where clues are helpful.     

Computation of Maximally Localized Wannier Functions using a simultaneous diagonalization algorithm

We show that a simultaneous diagonalization algorithm used in signal processing applications can be used in the context of electronic structure calculations to efficiently compute Maximally Localized Wannier Functions (MLWFs). Applications to calculations of MLWFs in molecular and solid systems demonstrate the efficiency of the approach. We also present and discuss a parallel version of the algorithm. An extension of the concept of MLWF to generalized minimum spread wavefunctions is proposed.     

Equivalence of <Emphasis Type="Italic">ε</Emphasis> -Approximate Separation and Optimization in Fixed Dimensions<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

Given a closed, convex set X\subseteq \bbR ⁿ , containing the origin, we consider the problem (P) : max {c^\T x\colon x ∈ X} . We show that, for a fixed dimension, n , and fixed \eps , 0 <\eps<1 , the existence of a combinatorial, strongly polynomial \eps -approximation separation algorithm for the set X is equivalent to the existence of a combinatorial, strongly polynomial \eps -approximation optimization algorithm for the problem (P) . Received June 5, 1996; revised September 25, 1997.     

Numerical ‘health check’ for scientific codes: the CADNA approach

Scientific computation has unavoidable approximations built into its very fabric. One important source of error that is difficult to detect and control is round-off error propagation which originates from the use of finite precision arithmetic. We propose that there is a need to perform regular numerical ‘health checks’ on scientific codes in order to detect the cancerous effect of round-off error propagation. This is particularly important in scientific codes that are built on legacy software. We advocate the use of the CADNA library as a suitable numerical screening tool. We present a case study to illustrate the practical use of CADNA in scientific codes that are of interest to the Computer Physics Communications readership. In doing so we hope to stimulate a greater awareness of round-off error propagation and present a practical means by which it can be analyzed and managed.     

Reactive Local Search for the Maximum Clique Problem<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

A new Reactive Local Search (\RLS ) algorithm is proposed for the solution of the Maximum-Clique problem. \RLS is based on local search complemented by a feedback (history-sensitive) scheme to determine the amount of diversification. The reaction acts on the single parameter that decides the temporary prohibition of selected moves in the neighborhood, in a manner inspired by Tabu Search. The performance obtained in computational tests appears to be significantly better with respect to all algorithms tested at the the second DIMACS implementation challenge. The worst-case complexity per iteration of the algorithm is O(max {n,m}) where n and m are the number of nodes and edges of the graph. In practice, when a vertex is moved, the number of operations tends to be proportional to its number of missing edges and therefore the iterations are particularly fast in dense graphs. Received September 11, 1997; revised February 5, 1998.     

A novel approach for the stability problem in non-linear dynamical systems

We present a methodology for the determination of sufficient conditions for the existence of a Lyapunov function in a general class of non-linear dynamical systems. The algorithm can be applied in the cases where the system parameters are numerically specified or not. The numerical algorithm involves the resolution of a linear programming problem. The algebraic version is implemented using the MAPLE programming system in the package Lyapunov.     

Robust estimation of a correlation coefficient for <Emphasis Type="Italic">ε</Emphasis>-contaminated bivariate normal distributions

Robust estimations of a correlation coefficient, based on: (i) direct robust analogues of a sample correlation coefficient, (ii) nonparametric estimations of correlation, (iii) robust regression, (iv) robust estimation of the major constituents of a variance, (v) stable estimation of parameters, and (vi) preliminary removal of outliers from data with the following application of a sample correlation coefficient to the residuary observations, are studied. Their application to contaminated normal models on small and large samples is studied, the best robust estimations from the suggested are pointed out.     

Fault Identification in System-Level Diagnosis: a Logic-Based Framework and an <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>2</Superscript>\sqrt{τ}/{\log <Emphasis Type="Italic">n</Emphasis>}) Algorithm

Much research has been devoted to system-level diagnosis—SLD. Two issues have been addressed. The first of these is diagnosability, i.e., provide necessary and sufficient conditions for a system of n units to be diagnosable provided that the number of faulty units does not exceed τ . The second is the design of fault identification algorithms, assuming that the system being considered is diagnosable. This paper focuses on the second of these concerns, discussing several algorithms of which the most efficient runs in O(n ^2.5 ) . By considering a logical framework, this paper investigates the process of fault identification and proposes a fault identification algorithm which runs in O( n ² \sqrt τ / \sqrt log n ) , τ < n/2 . Received January 10, 2000; revised August 3, 2000.     

QDENSITY—A Mathematica quantum computer simulation

This Mathematica 6.0 package is a simulation of a Quantum Computer. The program provides a modular, instructive approach for generating the basic elements that make up a quantum circuit. The main emphasis is on using the density matrix, although an approach using state vectors is also implemented in the package. The package commands are defined in Qdensity.m which contains the tools needed in quantum circuits, e.g., multiqubit kets, projectors, gates, etc.

New version program summary

Program title: QDENSITY 2.0Catalogue identifier: ADXH_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXH_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.: 26 055No. of bytes in distributed program, including test data, etc.: 227 540Distribution format: tar.gzProgramming language: Mathematica 6.0Operating system: Any which supports Mathematica; tested under Microsoft Windows XP, Macintosh OS X, and Linux FC4Catalogue identifier of previous version: ADXH_v1_0Journal reference of previous version: Comput. Phys. Comm. 174 (2006) 914Classification: 4.15Does the new version supersede the previous version?: Offers an alternative, more up to date, implementationNature of problem: Analysis and design of quantum circuits, quantum algorithms and quantum clusters.Solution method: A Mathematica package is provided which contains commands to create and analyze quantum circuits. Several Mathematica notebooks containing relevant examples: Teleportation, Shor's Algorithm and Grover's search are explained in detail. A tutorial, Tutorial.nb is also enclosed.Reasons for new version: The package has been updated to make it fully compatible with Mathematica 6.0Summary of revisions: The package has been updated to make it fully compatible with Mathematica 6.0Running time: Most examples included in the package, e.g., the tutorial, Shor's examples, Teleportation examples and Grover's search, run in less than a minute on a Pentium 4 processor (2.6 GHz). The running time for a quantum computation depends crucially on the number of qubits employed.     

Computation of the eigenvalues of the Schrödinger equation by exponentially-fitted Runge-Kutta-Nyström methods

In this work we consider exponentially fitted and trigonometrically fitted Runge-Kutta-Nyström methods. These methods integrate exactly differential systems whose solutions can be expressed as linear combinations of the set of functions exp(wx), exp(−wx), or sin(wx), cos(wx), w∈ℜ. We modify existing RKN methods of fifth and sixth order. We apply these methods to the computation of the eigenvalues of the Schrödinger equation with different potentials as the harmonic oscillator, the doubly anharmonic oscillator and the exponential potential.     

Efficient Algorithms for Integer Programs with Two Variables per Constraint<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

Given a bounded integer program with n variables and m constraints, each with two variables, we present an O(mU) time and O(m) space feasibility algorithm, where U is the maximal variable range size. We show that with the same complexity we can find an optimal solution for the positively weighted minimization problem for monotone systems. Using the local-ratio technique we develop an O(nmU) time and O(m) space 2 -approximation algorithm for the positively weighted minimization problem for the general case. We further generalize all results to nonlinear constraints (called axis-convex constraints ) and to nonlinear (but monotone) weight functions. Our algorithms are not only better in complexity than other known algorithms, but also considerably simpler, and they contribute to the understanding of these very fundamental problems. Received June 21, 1996; revised December 5, 1997.     

Group‐in‐a‐Box Meta‐Layouts for Topological Clusters and Attribute‐Based Groups: Space‐Efficient Visualizations of Network Communities and Their Ties

An important part of network analysis is understanding community structures like topological clusters and attribute‐based groups. Standard approaches for showing communities using colour, shape, rectangular bounding boxes, convex hulls or force‐directed layout algorithms remain valuable, however our Group‐in‐a‐Box meta‐layouts add a fresh strategy for presenting community membership, internal structure and inter‐cluster relationships. This paper extends the basic Group‐in‐a‐Box meta‐layout, which uses a Treemap substrate of rectangular regions whose size is proportional to community size. When there are numerous inter‐community relationships, the proposed extensions help users view them more clearly: (1) the Croissant–Doughnut meta‐layout applies empirically determined rules for box arrangement to improve space utilization while still showing inter‐community relationships, and (2) the Force‐Directed layout arranges community boxes based on their aggregate ties at the cost of additional space. Our free and open source reference implementation in NodeXL includes heuristics to choose what we have found to be the preferable Group‐in‐a‐Box meta‐layout to show networks with varying numbers or sizes of communities. Case study examples, a pilot comparative user preference study (nine participants), and a readability measure‐based evaluation of 309 Twitter networks demonstrate the utility of the proposed meta‐layouts.     

A Fortran code for null geodesic solutions in the Lema?&#x0302;tre-Tolman-Bondi spacetime

This paper describes the Fortran 77 code SIMU, version 1.1, designed for numerical simulations of observational relations along the past null geodesic in the Lema?&#x0302;tre-Tolman-Bondi (LTB) spacetime. SIMU aims at finding scale invariant solutions of the average density, but due to its full modularity it can be easily adapted to any application which requires LTB's null geodesic solutions. In version 1.1 the numerical output can be read by the GNUPLOT plotting package to produce a fully graphical output, although other plotting routines can be easily adapted. Details of the code's subroutines are discussed, and an example of its output is shown.     

The direct simulation Monte Carlo method applied to a Boltzmann-like vehicular traffic flow model

In this paper a direct simulation Monte Carlo (DSMC) method is applied to a spatial homogeneous mesoscopic vehicular traffic flow model, based on a Boltzmann-like master equation. In contrast to gas kinetics, where in a collision a velocity jump change occurs, the interaction now changes the acceleration value of the following car in a leading car pair. There are no conservation laws in a single interaction. Therefore the Bird simulation scheme seems not to be the right choice for the approximation of the interaction integral. It is shown that a Nanbu like scheme is natural for this process. To avoid the typical double loop computational effort of the Nanbu scheme, a sampling algorithm developed by Babovsky is applied. Several car interaction profiles are examined and their resulting stochastic equilibrium solutions are discussed. First, simple interaction profiles are used to compare the simulation results with analytic calculated velocity distributions showing excellent agreement. Second, a realistic distance threshold interaction profile is applied to the simulation and the results are shown to be in qualitative agreement with measured traffic flow data. The simulation procedure seems to be applicable to study the influence of different interaction profiles to the macroscopic vehicular traffic flow quantities in stochastic equilibrium.     

A simple “embedded” reasoning inference engine with application example in the X-ray Photoelectron Spectroscopy

In the field of experimental data acquisition and evaluation need rises for using some kind of “expert system” in order to provide support for sophisticated instruments and data evaluation applications. Different external expert system shells served as the basis for previous attempts to develop an expert system for such goals in the X-ray Photoelectron Spectroscopy (XPS). The paper presents a simple reasoning expert system engine, which can be built directly into data acquisition and evaluation software. Some problems arising due to the lack of human intelligence in the inferencing process are also discussed. The feasibility of the realized system is demonstrated through implementing a real-life rule set, an example (the carbon contamination rules) taken from the field of XPS. Apart from the field-specific rules, the package can be used on any field.     

Fast LP method for the Schrödinger equation

The LP and CP methods are two versions of the piecewise perturbation methods to solve the Schrödinger equation. On each step the potential function is approximated by a constant (for CP) or by a linear function (for LP) and the deviation of the true potential from this approximation is treated by the perturbation theory.This paper is based on the idea that an LP algorithm can be made faster if expressed in a CP-like form. We obtain a version of order 12 whose two main ingredients are a new set of formulae for the computation of the zeroth-order solution which replaces the use of the Airy functions, and a convenient way of expressing the formulae for the perturbation corrections. Tests on a set of eigenvalue problems with a very big number of eigenvalues show that the proposed algorithm competes very well with a CP version of the same order and is by one order of magnitude faster than the LP algorithms existing in the literature. We also formulate a new technique for the step width adjustment and bring some new elements for a better understanding of the energy dependence of the error for the piecewise perturbation methods.     

On identification of the arterial model parameters from experiments applicable “in vivo”

We present a parameter identification procedure developed for a composite model of arterial wall which is characterized by collagen viscoelastic fibres embedded in hyperelastic incompressible matrix. The structure undergoes large deformation described using the total Lagrangian formulation. In the paper the identification procedure is tested numerically when applied to a simulated vessel dynamic inflation test, which can be performed in vivo. A stability test of the identification method is pursued as illustrated by two examples: the creep and relaxation tests.