The numerical solution ofẊ = A_{1}X + XA_{2} + D, X(0) = C

An improved method of solving the general matrix differential equationdot{X} = A_{1}X + XA_{2} + D, X(0) = CforXis considered where A1and A2are stable matrices. The algorithm proposed requires only5n^{2}words of memory and converges in approximately43n^{3} mus where μ is the multiplication time of the digital computer andn = max(n_{1},n_{2})whereA_{1} in R^{n_{1} times n_{1}}, A_{2} in R^{n_{2} times n_{2}}. The algorithm is extremely simple to implement.     

On the computation of Tricomi's ψ function

Two methods for calculating Tricomi's confluent hypergeometric function are discussed. Both methods are based on recurrence relations. The first method converges like $$\exp ( - \alpha |\lambda |^{1/3} n^{2/3} )for some \alpha > 0$$ and the second like $$\exp ( - \beta |\lambda |^{1/2} n^{1/2} )for some \beta > 0.$$ Several examples are presented.     

Numerical solution of the matrix equation AX + XAT+ B = 0

A recursive algorithm is shown to solve the above equation accurately for large (n leq 146), lightly damped (zeta geq 10^{-3}) systems. About2.5n^{2}storage locations are required, and about2.5n^{3}multiplications are performed per recursion, ten recursions being typical.     

Finding Pathway Structures in Protein Interaction Networks

The increased availability of data describing biological interactions provides important clues on how complex chains of genes and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find an optimal path structure in time and space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure. Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures, we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity by applying it to protein interaction networks in the DIP database.     

Subquadratic Algorithms for 3SUM

We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of . In the circuit RAM with one nonstandard AC ⁰ operation, we obtain . In external memory, we achieve O(n ²/(MB)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of . In all cases, our speedup is almost quadratic in the “parallelism” the model can afford, which may be the best possible. Our algorithms are Las Vegas randomized; time bounds hold in expectation, and in most cases, with high probability.     

A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time [(O)\tilde](n²s^w/2-1)\widetilde{O}(n^{2}s^{\omega/2-1}), where the input matrices have size n×n, the number of non-zero entries in the product matrix is at most s, ω is the exponent of the fast matrix multiplication and [(O)\tilde](f(n))\widetilde{O}(f(n)) denotes O(f(n)log  ^d n) for some constant d. By the currently best bound on ω, its running time can be also expressed as [(O)\tilde](n²s^0.188)\widetilde{O}(n^{2}s^{0.188}). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n ^1.232 and it is never slower than the fast [(O)\tilde](n^w)\widetilde{O}(n^{\omega})-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form [(O)\tilde](n^{w(\frac12log_ns,1,1)})\widetilde{O}(n^{\omega(\frac{1}{2}\log_{n}s,1,1)}), where ω(p,q,t) is the exponent of the fast multiplication of an n ^p ×n ^q matrix by an n ^q ×n ^t matrix.     

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of 3\frac1318 n² + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of 1\frac56 n² - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of \frac56 n² + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5\frac34n²+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of \frac18n²-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of 1\frac12n² + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n ²−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.     

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

In this paper, we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds, we obtain lower bounds for these models.For depth-3 multilinear formulas, of size exp\({(n^\delta)}\), we give a hitting set of size exp\({\left(\tilde{O}\left(n^{2/3 + 2\delta/3}\right) \right)}\). This implies a lower bound of exp\({(\tilde{\Omega}(n^{1/2}))}\) for depth-3 multilinear formulas, for some explicit polynomial.For depth-4 multilinear formulas, of size exp\({(n^\delta)}\), we give a hitting set of size exp\({\left(\tilde{O}\left(n^{2/3 + 4\delta/3}\right) \right)}\). This implies a lower bound of exp\({(\tilde{\Omega}(n^{1/4}))}\) for depth-4 multilinear formulas, for some explicit polynomial.A regular formula consists of alternating layers of \({+,\times}\) gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp\({\left(n^{1- \delta}\right)}\), for regular depth-d multilinear formulas with formal degree at most n and size exp\({(n^\delta)}\), where \({\delta = O(1/{\sqrt{5}^d})}\). This result implies a lower bound of roughly exp\({(\tilde{\Omega}(n^{1/{\sqrt{5}^d}}))}\) for such formulas.We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known.Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas, we go straight to read-once algebraic branching programs).     

Cancellations in multivariable continuous-time and discrete-time feedback systems treated by greatest common divisor extraction

This correspondence considers a multivariable system with proper rational matrix transfer functions G0and Gfin the forward and feedback branches, respectively. It develops a strictly algebraic procedure to obtain polynomials whose zeros are the poles of the matrix transfer functions from input to output (Hy), and from input to error (He). G0and Gfare given in the polynomial matrix factored formN_{0}D_{0}^{-1}andD_{f}^{-1}N_{f}. The role of the assumption det [I + G_{f}(infty)G_{0}(infty)] neq 0and the relation between the zeros of det [I + G_{f}G_{0}] and the poles of Hyand Heare indicated. The implications for stability analysis of continuous-time as well as discrete-time systems are stressed.     

A Class of Linear Positive Maps in Matrix Algebras

A class of linear positive, trace preserving maps in M _n is given in terms of affine maps in which map the closed unit ball into itself.     

A parametric algorithm for semigroup computation on mesh with buses

In this paper, we present a new parametric parallel algorithm for semigroup computation on mesh with reconfigurable buses (MRB). Givenn operands, our parallel algorithm can be performed in $O(2^{(2c^2 + 3c)/(4c + 1)} n^{1/(8c + 2)} )$ , time on a $2^{(c^2 - c)/(8c + 2)} n^{(5c + 1)/(8c + 2)} \times 2^{(c - c^2 )/(8c + 2)} n^{(3c + 1)/(8c + 2)} $ MRB ofn processors, where $0 \leqslant c \leqslant O(\sqrt {\log _2 n} )$ . Specifically, whenc=0, it takes $O(\sqrt n )$ time on the $\sqrt n \times \sqrt n $ MRB and is equal to the result on the mesh-connected computers; whenc=1, it takesO(n ^1/10) time on then ^3/5×n ^2/5 MRB and is equal to the previous result on the mesh-connected computers with segmented multiple buses; whenc=2, it takesO(n ^1/18) time on the 2^1/9 n ^11/18×2^(?1/9) n ^7/18 MRB; when $O(\sqrt {\log _2 n} )$ , it takesO(log₂ n) time and is equal to the previous result on the MRB. Consequently, our results can be viewed as a unification of some best known results on different parallel computational models.     

Yang-Baxter {\breve R} matrix, entanglement and Yangian

We present a method to construct ??X?? form unitary Yang-Baxter ${\breve R}$ matrices, which act on the tensor product space ${V_{i}^{j_{1}}\otimes V_{i+1}^{j_{2}}}$ . We can obtain a set of entangled states for (2j ₁?+?1)?× (2j ₂?+?1)-dimensional system with these Yang-Baxter ${\breve R}$ matrices. By means of Yang-Baxter approach, a 8?× 8 Yang-Baxter Hamiltonian is constructed. Yangian symmetry and Yangian generators as shift operators for this Yang-Baxter system are investigated in detail.     

Internal stabilization and decoupling in linear multivariable systems by unity output feedback compensation

We consider the problem of internally stabilizing and simultaneously diagonally decoupling a linear multivariable system by unity output feedback compensation. A sufficient condition is derived for the existence of a cascade proper compensatorC(s)such that when employed in a unity feedback loop involving the proper transfer function matrix Poof a free of unstable hidden modes systemSigma(P_{o}), will not only internally stabilize the feedback closed-loop systemSigma(P_{o}, C)but will also give rise to a closed-loop transfer function matrixH_{yr}^{diag}, which is nonsingular, diagonal, and has desired poles. Based on this analysis, an algorithmic procedure for the computation of such a compensator is presented.     

Sulle formule di quadratura di Tschebyscheff

For the Tschebyscheff quadrature formula: $$\int\limits_{ - 1}^1 {\left( {1 - x^2 } \right)^{\lambda - 1/2} f(x) dx} = K_n \sum\limits_{k = 1}^n {f(x_{n,k} )} + R_n (f), \lambda > 0$$ it is shown that the degre,N, of exactness is bounded by: $$N \leqslant C(\lambda )n^{1/(2\lambda + 1)} $$ whereC(λ) is a convenient function of λ. For λ=1 the complete solution of Tschebyscheff's problem is given.     

A stable state-space realization in the formulation of H∞norm computation

In the two block H^inftyoptimization problem, usually we are given the state-space realizations of the proper rational matricesR_{1}(s)andR_{2}(s)whose poles are all the open right-half plane. Two problems are studied in the note. The first is the evaluation ofphi(s)R_{1}(s)ats = s_{k}, k = 1, 2, ..., n, wherephi(s)is an inner function whose zeros{s_{k}, k = 1, 2, ..., n }are the poles ofR_{1}(s). This evaluation is essential if Chang and Pearson's method is used for computing the optimal H^inftynorm. The problem is solved in state space via the solutions of Lyapunov equations. Neither polynomial matrix manipulations nor numerical pole-zero cancellations are involved in the evaluation. The second problem is to find a stable state-space realization ofS(s) = U(s)R_{2}(s)whereU(s)is an inner matrix. This problem arises in the spectral factorization ofgamma^{2} - R_{2}^{ast}R_{2}. Doyle and Chu had a method for constructing stableS(s)based on a minimal realization ofR_{2}(s). An alternate method is proposed. The alternate method does not require a minimal realization ofR_{2}(s)and only a Lyapunov equation is involved.     

The Cache Complexity of Multithreaded Cache Oblivious Algorithms

We present a technique for analyzing the number of cache misses incurred by multithreaded cache oblivious algorithms on an idealized parallel machine in which each processor has a private cache. We specialize this technique to computations executed by the Cilk work-stealing scheduler on a machine with dag-consistent shared memory. We show that a multithreaded cache oblivious matrix multiplication incurs cache misses when executed by the Cilk scheduler on a machine with P processors, each with a cache of size Z, with high probability. This bound is tighter than previously published bounds. We also present a new multithreaded cache oblivious algorithm for 1D stencil computations incurring cache misses with high probability, one for Gaussian elimination and back substitution, and one for the length computation part of the longest common subsequence problem incurring cache misses with high probability. This work was supported in part by the Defense Advanced Research Projects Agency (DARPA) under contract No. NBCH30390004.     

Dynamic, unbalanced distribution of tasks on a PS3 cluster system for double precision calculation

The article aims to describe an algorithm for dynamic distribution of tasks in a parallel computing system consisting of a network of 9 PlayStation3 (PS3) stations. Due to the fact that the SPU cores do not have units of double precision calculation, these calculations require a longer time. Therefore, an unbalanced distribution of computing tasks on a heterogeneous cluster system as 9×PS3 is necessary. The algorithm produces an estimation of the value of ?? by calculating the integral $\pi= \int_{0}^{1} \frac{4}{1+x^{2}}$ and makes PPU-SPU empirical distribution of tasks on a smaller number of intervals. After determining the optimum loading between cores 18×PPU (PowerPC Unit) and 54×SPU (Synergetic Processor Unit), the integral calculation algorithm goes to a larger number of intervals.     

Stability conditions for annth-order nonlinear time-varying differential system

The stability of a system described by thenth-order differential equationy^(n) + a_{n-1}Y^(n-1) + ... + a_{1}dot{Y} + a_{0}y = 0wherea_{i} = a_{i}(t, y, dot{y}, ... , y^(n-1)),i = 0,1,2, ... , n-1is considered. It is shown that if the instantaneous roots of the characteristic equation of the system are always contained in a circle on the complex plane with center (- z, 0),z > 0and radius ω such thatfrac{z}{Omega} > {{1, n = 1}{sqrt{2n(n-1)}, n geq 2}then the system is uniformly asymptotically stable in the sense of Liapunov.     

A note on pole assignment

This note gives an alternate proof of Davison's theorem [2] on pole placement and further shows that, for a controllable, observable systemdot{x} = hat{A}x + hat{B}u, y = hat{C}x, the number of poles that can be assigned arbitrarily are equal to max (m,p), wheremRankhat{B}andp= Rankhat{C}. In some cases, more than max (m,p) poles can be assigned arbitrarily.