Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

Reduced Collocation Methods: Reduced Basis Methods in the Collocation Framework

In this paper, we present the first reduced basis method well-suited for the collocation framework. Two fundamentally different algorithms are presented: the so-called Least Squares Reduced Collocation Method (LSRCM) and Empirical Reduced Collocation Method (ERCM). This work provides a reduced basis strategy to practitioners who prefer a collocation, rather than Galerkin, approach. Furthermore, the empirical reduced collocation method eliminates a potentially costly online procedure that is needed for non-affine problems with Galerkin approach. Numerical results demonstrate the high efficiency and accuracy of the reduced collocation methods, which match or exceed that of the traditional reduced basis method in the Galerkin framework.     

On the use of parallel processors for implicit Runge-Kutta methods

An iteration scheme, for solving the non-linear equations arising in the implementation of implicit Runge-Kutta methods, is proposed. This scheme is particularly suitable for parallel computation and can be applied to any method which has a coefficient matrixA with all eigenvalues real (and positive). For such methods, the efficiency of a modified Newton scheme may often be improved by the use of a similarity transformation ofA but, even when this is the case, the proposed scheme can have advantages for parallel computation. Numerical results illustrate this. The new scheme converges in a finite number of iterations when applied to linear systems of differential equations, achieving this by using the nilpotency of a strictly lower triangular matrixS ^?1 AS — Λ, with Λ a diagonal matrix. The scheme reduces to the modified Newton scheme whenS ^?1 AS is diagonal.A convergence result is obtained which is applicable to nonlinear stiff systems.     

ADER Schemes for Nonlinear Systems of Stiff Advection�CDiffusion�CReaction Equations

In this article we extend the high order ADER finite volume schemes introduced for stiff hyperbolic balance laws by Dumbser, Enaux and Toro (J. Comput. Phys. 227:3971?C4001, 2008) to nonlinear systems of advection?Cdiffusion?Creaction equations with stiff algebraic source terms. We derive a new efficient formulation of the local space-time discontinuous Galerkin predictor using a nodal approach whose interpolation points are tensor-products of Gauss?CLegendre quadrature points. Furthermore, we propose a new simple and efficient strategy to compute the initial guess of the locally implicit space-time DG scheme: the Gauss?CLegendre points are initialized sequentially in time by a second order accurate MUSCL-type approach for the flux term combined with a Crank?CNicholson method for the stiff source terms. We provide numerical evidence that when starting with this initial guess, the final iterative scheme for the solution of the nonlinear algebraic equations of the local space-time DG predictor method becomes more efficient. We apply our new numerical method to some systems of advection?Cdiffusion?Creaction equations with particular emphasis on the asymptotic preserving property for linear model systems and the compressible Navier?CStokes equations with chemical reactions.     

Vasil’ev codes of length n = 2m and doubling of Steiner systems S(n, 4, 3) of a given rank

Extended binary perfect nonlinear Vasil’ev codes of length n = 2^m and Steiner systems S(n, 4, 3) of rank n-m over F ₂ are studied. The generalized concatenated construction of Vasil’ev codes induces a variant of the doubling construction for Steiner systems S(n, 4, 3) of an arbitrary rank r over F ₂. We prove that any Steiner system S(n = 2^m, 4, 3) of rank n-m can be obtained by this doubling construction and is formed by codewords of weight 4 of these Vasil’ev codes. The length 16 is studied in detail. Orders of the full automorphism groups of all 12 nonequivalent Vasil’ev codes of length 16 are found. There are exactly 15 nonisomorphic systems S(16, 4, 3) of rank 12 over F ₂, and they can be obtained from codewords of weight 4 of the extended Vasil’ev codes. Orders of the automorphism groups of all these Steiner systems are found.     

On time-space classes and their relation to the theory of real addition

A new lower bound on the computational complexity of the theory of real addition and several related theories is established: any decision procedure for these theories requires either space 2^εn or nondeterministic time 2^εn2 for some constant ε0 and infinitely many n.The proof is based on the families of languages TISP(T(n), S(n)) which can be recognized simultaneously in time T(n) and S(n) and the conditions under which they form a hierarchy.     

A divide-and-conquer direct differentiation approach for multibody system sensitivity analysis

In the design and analysis of multibody dynamics systems, sensitivity analysis is a critical tool for good design decisions. Unless efficient algorithms are used, sensitivity analysis can be computationally expensive, and hence, limited in its efficacy. Traditional direct differentiation methods can be computationally expensive with complexity as large as O(n ⁴+n ² m ²+nm ³), where n is the number of generalized coordinates in the system and m is the number of algebraic constraints. In this paper, a direct differentiation divide-and-conquer approach is presented for efficient sensitivity analysis of multibody systems with general topologies. This approach uses a binary tree structure to traverse the topology of the system and recursively generate the sensitivity data in linear and logarithmic complexities for serial and parallel implementations, respectively. This method works concurrently with the forward dynamics problem, and hence, requires minimal data storage. The differentiation required in this algorithm is minimum as compared to traditional methods, and is generated locally on each body as a preprocessing step. The method provides sensitivity values accurately up to integration tolerance and is insensitive to perturbations in design parameter values. This approach is a good alternative to existing methodologies, as it is fairly simple to implement for general topologies and is computationally efficient.     

An algorithm for computing the restriction scaffold assignment problem in computational biology

Let S and T be two finite sets of points on the real line with |S|+|T|=n and |S|>|T|. The restriction scaffold assignment problem in computational biology assigns each point of S to a point of T such that the sum of all the assignment costs is minimized, with the constraint that every element of T must be assigned at least one element of S. The cost of assigning an element si of S to an element tj of T is |si−tj|, i.e., the distance between si and tj. In 2003 Ben-Dor, Karp, Schwikowski and Shamir [J. Comput. Biol. 10 (2) (2003) 385] published an O(nlogn) time algorithm for this problem. Here we provide a counterexample to their algorithm and present a new algorithm that runs in O(n²) time, improving the best previous complexity of O(n³).     

Generalized Preparata codes and 2-resolvable Steiner quadruple systems

We consider generalized Preparata codes with a noncommutative group operation. These codes are shown to induce new partitions of Hamming codes into cosets of these Preparata codes. The constructed partitions induce 2-resolvable Steiner quadruple systems S(n, 4, 3) (i.e., systems S(n, 4, 3) that can be partitioned into disjoint Steiner systems S(n, 4, 2)). The obtained partitions of systems S(n, 4, 3) into systems S(n, 4, 2) are not equivalent to such partitions previously known.     

Gauss–Newton Multilevel Methods for Least-Squares Finite Element Computations of Variably Saturated Subsurface Flow

We apply the least-squares mixed finite element framework to the nonlinear elliptic problems arising in each time-step of an implicit Euler discretization for variably saturated flow. This approach allows the combination of standard piecewise linear H ¹-conforming finite elements for the hydraulic potential with the H(div)-conforming Raviart–Thomas spaces for the flux. It also provides an a posteriori error estimator which may be used in an adaptive mesh refinement strategy. The resulting nonlinear algebraic least-squares problems are solved by an inexact Gauss–Newton method using a stopping criterion for the inner iteration which is based on the change of the linearized least-squares functional relative to the nonlinear least-squares functional. The inner iteration is carried out using an adaptive multilevel method with a block Gauss–Seidel smoothing iteration. For a realistic water table recharge problem, the results of computational experiments are presented. Received January 4, 1999; revised July 19, 1999     

A recursive formulation of collocation in terms of canonical polynomials

In this paper we discuss two related but analytically different techniques: the collocation method and Ortiz's recursive formulation of the Tau Method. Specifically, we show that it is possible to simulate with the Tau Method collocation approximants for any desired degree. We give a representation for collocation approximants in terms ofshifted canonical polynomials, which are introduced here. We show that in the linear case computing a collocation approximant of orderN by this new approach requiresO(N) arithmetic operations while obtaining the same approximant by the direct approach involvesO(N ³). Furthermore, our technique leads to a recursive formulation of collocation. We discuss separately the linear and nonlinear cases and propose a more efficienteconomized approach for the latter.     

A molecular solution to the hitting-set problem in DNA-based supercomputing

Assume that there exists a collection C of subsets of a finite set S, and a positive integer K ? ∣S∣, and we need to know whether there is a subset S′ ⊆ S with ∣S′∣ ? K such that S′ contains at least one element of each subset in C. In other words, S′ is the subset that intersects every subset in C and is called the hitting-set. In this paper, a DNA-based algorithm is proposed to solve the small hitting-set problem. A small hitting-set is a hitting-set with the smallest K value, i.e., the hitting-set with the smallest number of elements. Furthermore, another algorithm is introduced to find the number of ones from 2ⁿ combinations and minimum numbers of ones represents the small hitting-set since K is expected to be as small as possible. The complexity of the proposed DNA-based algorithm is discussed, in terms of time complexity, volume complexity, numbers of test tube used and the longest library strand in solution space. Finally, the simulated experiment is applied to verify the correctness of our proposed DNA-based algorithm, in order to solve the well-known hitting-set problem.     

On the error structure of the implicit Euler scheme applied to stiff systems of differential equations

In this paper we investigate the structure of the global discretization error of the implicit Euler scheme applied to systems to stiff differential equations, extending earlier work on this subject (cf. [1], [9]). We restrain our considerations to the linear, self-adjoint, constant coefficient case but—in contrast to [1], [9]—we make no assumptions about the nature of the stiff spectrum; the stiff eigenvalues may be arbitrarily distributed on the negative real axis. Our main result says that the global error of the implicit Euler scheme admits an asymptotic expansion in powers of the stepsize τ which is not asymptotically correct in the conventional sense: Near the initial pointt=0 the expansion is spoiled at theO(τ²) by ‘irregular’ error components which are, however, (algebraically) damped, such that away fromt=0 the ‘pure’ asymptotic expansion reappears. We present numerical experiments confirming this result. Our considerations should be particularly helpful for a rigorous, quantitative analysis of the structure of the full (space & time) discretization error in the PDE (method of lines) context, and thus for a sound theoretical justification of extrapolation techniques for this important class of stiff problems.     

Embedding meshes into twisted-cubes

The n-dimensional twisted-cube, TN_n, is a variation of the hypercube. In this paper, we study embedding of meshes into TN_n. We prove three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded into TN_n with dilation 1 and expansion 1. (2) For any integer n ? 4, an m × k(m ? 3, k ? 3) mesh cannot be embedded into TN_n with dilation 1. (3) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded into TN_n with dilation 2 and expansion 1.     

Lipschitzian De Morgan triplets of fuzzy connectives

After studying Lipschitzian strong negations, Lipschitzian De Morgan triplets (T, S, n), where T is a triangular norm, S a triangular conorm, and n a strong negation, are investigated. The relationships between the best Lipschitzian constants of functions T, S and n are given. Several examples are included.     

Embedding meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ_n(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in LTQ_n with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in LTQ_n with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4  × (2ⁿ⁻² − 1) mesh can be embedded in LTQ_n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.     

Spectral stability based event localizing temporal decomposition

In this paper a new approach to Temporal Decomposition (TD) of speech, called Spectral Stability Based Event Localizing Temporal Decomposition (S²BEL-TD), is presented. The original method of TD proposed by Atal (1983, Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, 81–84) is known to have the drawbacks of high computational cost, and the high parameter sensitivity of the number and locations of events. In S²BEL-TD, the event localization is performed based on a maximum spectral stability criterion. This overcomes the high parameter sensitivity of events of Atal’s method. Also, S²BEL-TD avoids the use of the computationally costly singular value decomposition routine used in Atal’s method, thus resulting in a computationally simpler algorithm for TD. Simulation results show that an average spectral distortion of about 1.5 dB can be achieved with line spectral frequencies as the spectral parameter. It is shown that the temporal pattern of the speech excitation parameters can also be well described using the S²BEL-TD technique.     

A comparison of point and ball iterations in the contractive mapping case

In applications, one of the basic problems is to solve the fixed point equationx=Tx withT a contractive mapping. Two theorems which can be implemented computationally to verify the existence of a solutionx ^* to the equation and to obtain a convergent approximate solution sequence {x _n } are the classical Banach contraction mapping theorem and the newly established global convergence theorem of the ball algorithms in You, Xu and Liu [16]. These two theorems are compared on the basis of sensitivity, precision, computational complexity and efficiency. The comparison shows that except for computational complexity, the latter theorem is of far greater sensivity, precision and computational efficiency. This conclusion is supported by a number of numerical examples.     

Training SVMs on a bound vectors set based on Fisher projection

Standard support vector machines (SVMs) training algorithms have O(l ³) computational and O(l ²) space complexities, where l is the training set size. It is thus computationally infeasible on very large data sets. To alleviate the computational burden in SVM training, we propose an algorithm to train SVMs on a bound vectors set that is extracted based on Fisher projection. For linear separate problems, we use linear Fisher discriminant to compute the projection line, while for non-linear separate problems, we use kernel Fisher discriminant to compute the projection line. For each case, we select a certain ratio samples whose projections are adjacent to those of the other class as bound vectors. Theoretical analysis shows that the proposed algorithm is with low computational and space complexities. Extensive experiments on several classification benchmarks demonstrate the effectiveness of our approach.     

A Direct Approach to Computing theμ-basis of Planar Rational Curves

This paper presents an O(n²) algorithm, based on Gröbner basis techniques, to compute the μ -basis of a degree n planar rational curve. The prior method involved solving a set of linear equations whose complexity by standard numerical methods was O(n³). The μ -basis is useful in computing the implicit equation of a parametric curve and can express the implicit equation in the form of a determinant that is smaller than that obtained by taking the resultant of the parametric equations.