Search

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is O(V), where V is the number of nodes in the network. The message size used by the algorithm is O(log ∣ID∣) where ∣ID∣ is the size of the name space of the nodes. Typically, log ∣ID∣ = O(log V). Previous algorithms that adapt to dynamic networks involved Ω(E) messages per topological change-inherently paying for re-computation of the tree from scratch. Spanning trees are essential components in many distributed algorithms. Some examples include broadcast (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection, and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions. [ABSTRACT FROM AUTHOR]

The article discusses various abstract domain variants for affine-relation analysis (ARA) and its relation. Information regarding the interconversion methods for the abstract domains of King/Søndergaard (KS) and Müller-Olm/Seidl (MOS) is provided. Also mentioned are the options for performing ARA in a program analyzer.

A code is presented which offers a simple clean way to get output that is very easy to read. Special support is given for the output of error messages which are a part of an application package or subprogram library. The code uses many of the features in Fortran 2003, and the "NEWUNIT=" in an open statement from Fortran 2008. The latter can easily be replaced with "UNIT=99". One goal here is to illustrate some of the nice features in recent incarnations of Fortran. [ABSTRACT FROM AUTHOR]

Software to compute angular and radial Mathieu functions is provided in the case that the parameter q is a complex variable and the independent variable x is real. After an introduction on the notation and the definitions of Mathieu functions and their related properties, Fortran 90 subroutines to compute them are described and validated with some comparisons. A sample application is also provided. [ABSTRACT FROM AUTHOR]

The SPQR_RANK package contains routines that calculate the numerical rank of large, sparse, numerically rank-deficient matrices. The routines can also calculate orthonormal bases for numerical null spaces, approximate pseudoinverse solutions to least squares problems involving rank-deficient matrices, and basic solutions to these problems. The algorithms are based on SPQR from SuiteSparseQR (ACM Transactions on Mathematical Software 38, Article 8, 2011). SPQR is a high-performance routine for forming QR factorizations of large, sparse matrices. It returns an estimate for the numerical rank that is usually, but not always, correct. The new routines improve the accuracy of the numerical rank calculated by SPQR and reliably determine the numerical rank in the sense that, based on extensive testing with matrices from applications, the numerical rank is almost always accurately determined when our methods report that the numerical rank should be correct. Reliable determination of numerical rank is critical to the other calculations in the package. The routines work well for matrices with either small or large null space dimensions. [ABSTRACT FROM AUTHOR]

Four routines called DPOTF3i, i = a,b,c,d, are presented. DPOTF3i are a novel type of level-3 BLAS for use by BPF (Slocked Packed format) Cholesky factorization and LAPACK routine DPOTRF Performance of routines DPOTF3i are still increasing when the performance of Level-2 routine DPOTF2 of LAPACK starts decreasing. This is our main result and it implies, due to the use of larger block size nb, that DGEMM, DSYRK, and DTRSM performance also increases! The four DPOTF3i routines use simple register blocking. Different platforms have different numbers of registers. Thus, our four routines have different register blocking sizes. BPF is introduced. LAPACK routines for POTRF and PPTRF using BPF instead of full and packed format are shown to be trivial modifications of LAPACK POTRF source codes. We call these codes BPTRF. There are two variants of BPF: lower and upper. Upper BPF is "identical" to Square Block Packed Format (SBPF). "LAPACK" implementations on multicore processors use SBPF Lower BPF is less efficient than upper BPF. Vector inplace transposition converts lower BPF to upper BPF very efficiently. Corroborating performance results for DPOTF3i versus DPOTF2 on a variety of common platforms are given for n & nb as well as results for large n comparing DBPTRF versus DPOTRF. [ABSTRACT FROM AUTHOR]

When societies experience disruption as caused by natural disasters, various official government agencies, relief organizations, and emergent citizen groups engage in activities that aid in the recovery effort-the process that leads to the resumption of normal life. In war environments however, societal trust can be affected and people may develop distrust of the institutions and associated individuals that provide and resolve breakdowns in infrastructure. This article reports on an ethnographic study of the use of information and communication technologies (ICTs) by citizens experiencing ongoing disruption in a conflict zone. We conducted 90 semistructured interviews with Iraqi civilians who experienced the 2nd Gulf War beginning in March 2003. We show how citizens used ICTs to continuously resolve breakdowns in infrastructure during ongoing disruption caused by the conflict, by creating new, reliable technology-mediated social arrangements that enabled people to maintain daily routines for travel, education, and obtaining information. We then discuss new ways to think about infrastructure and implications for the disaster relief effort. [ABSTRACT FROM AUTHOR]

We present a sound, complete and implementable tableau method for deciding satisfiability of formulas in the propositional version of computation tree logic CTL*. This is the first such tableau. CTL* is an exceptionally important temporal logic with applications from hardware design to agent reasoning, but there is no easily automated reasoning approach to CTL*. The tableau here is a traditional tree-shaped or top-down style tableau, and affords the possibility of reasonably quick decisions on the satisfiability of medium-sized formulas and construction of small models for them. A straightforward subroutine is given for determining when looping allows successful branch termination, but much needed further development is left as future work. In particular, a more general repetition prevention mechanism is needed to speed up the task of tableau construction. [ABSTRACT FROM AUTHOR]

We develop an incremental tableau-based decision procedure for the alternating-time temporal logic ATL and some of its variants. While running within the theoretically established complexity upper bound, we believe that our tableaux are practically more efficient in the average case than other decision procedures for ATL known so far. Besides, the ease of its adaptation to variants of ATL demonstrates the flexibility of the proposed procedure. [ABSTRACT FROM AUTHOR]

We present subroutines for the Cholesky factorization of a positive-definite symmetric matrix and for solving corresponding sets of linear equations. They exploit cache memory by using the block hybrid format proposed by the authors in a companion article. The matrix is packed into n(n + 1)/2 real variables, and the speed is usually better than that of the LAPACK algorithm that uses full storage (n2 variables). Included are subroutines for rearranging a matrix whose upper or lower-triangular part is packed by columns to this format and for the inverse rearrangement. Also included is a kernel subroutine that is used for the Cholesky factorization of the diagonal blocks since it is suitable for any positive-definite symmetric matrix that is small enough to be held in cache. We provide a comprehensive test program and simple example programs. [ABSTRACT FROM AUTHOR]

A translation to Fortran 90 of Gertrude Blanch's algorithm for computing the expansion coefficients of the series that represent Mathieu functions is presented. Its advantages are portability, higher precision, practicality of use, and extended documentation. In addition, numerical validations and comparisons with other existing methods are presented. [ABSTRACT FROM AUTHOR]

We present a program-generation approach to address a software-reuse challenge in the area of scientific computing. More specifically, we describe the design of a program generator for the specification of subroutines that can be generic in the dimensions of arrays, parameter lists, and called subroutines. We describe the application of that approach to a real-world problem in scientific computing which requires the generic description of inverse ocean modeling tools. In addition to a compiler that can transform generic specifications into efficient Fortran code for models, we have also developed a type system that can identify possible errors already in the specifications. This type system is important for the acceptance of the program generator among scientists because it prevents a large class of errors in the generated code. [ABSTRACT FROM AUTHOR]

Proposes FORTRAN subroutines for approximately solving the feedback vertex and arc set problems on directed graphs using a Greedy Randomized Adaptive Search Procedure (GRASP). Usage of the subroutines; Property of the GRASP algorithm.

Presents information on four Fortran subroutines for nondifferentiable optimization. Description of each subroutine; Sequential quadratic programming methods for nonlinear minimax optimization; Bundle-type methods for nonsmooth optimization.

Presents a study which described subroutines for generating preconditioners for the conjugate gradient method. Use of the subroutines in linear systems; Overview of the quasi-Newton preconditioners; Results of the study.

Explains some of the changes that have been incorporated in the LAPACK subroutine for reducing a symmetric banded matrix to tridiagonal form. Banded singular value decomposition problem; Banded symmetric positive definite generalized eigenvalue problem; Accumulation of transformations for the reduction to bidiagonal form.

Presents the design, implementation and interface of a library of Basic Linear Algebra Subroutines for sparse matrices (PSBLAS) which is specifically tailored to distributed-memory computers. PSBLAS library components hierarchy; Main PSBLAS data structures; Operations in the PSBLAS library.

Discusses the modification of subroutines in EISPACK and LAPACK for finding a few of the eigenvalues of a symmetric tridiagonal matrix. Relative difference of various smallest eigenvalues of principal minors to the full matrix; Course for the smallest eigenvalue; First three modes of the fiber problem.

Deals with a study which described LAPACK-based Fortran 77 subroutines for the reduction of a Hamiltonian matrix to square-reduced form and the approximation of all its eigenvalues using the implicit version of Van Loan's method. Description of the Van Loan's square-reduced method; Implementation of the algorithm; Numerical examples of the study.

Presents information on a study which proposed the use of typing rules to describe the subroutines in bytecode verifier of the Java Virtual Machine Language (JVML). Analysis of JVML subroutines and type system; Challenges pose by the subroutines to the design of a type system for JVML; Semantics and syntaxes of JVML.

Presents information on a study which described Fortran subroutines for finding approximate solutions of the maximum planar subgraph problem (graph planarization) using a Greedy Randomized Adaptive Search Procedure (GRASP). Information on graph planarization; GRASP for graph planarization; Design and implementation of the subroutines; Usage of the subroutines; Computational results.

New direction in Artificial Intelligence research have led to the need for certain novel features to be embedded in programming languages. This paper gives an overview of the nature of these features, and their implementation in four principal families of AI languages: SAIL; PLANNER/CONNIVER; QLISP/INTERLISP; AND POPLER/POP-2. The programming features described include: new data types and accessing mechanisms for stored expressions; more flexible control structures, including multiple processes and backtracking; pattern matching to allow comparison of data item with a template, and extraction of labeled subexpressions; and deductive mechanisms which allow the programming system to carry out certain activities including modifying the data base and deciding which subroutines to run next using only constraints and guidelines set up by the programmer. [ABSTRACT FROM AUTHOR]

We show that the Fortran source code for Algorithm 815 contains an error and we propose a correction. The error may cause the algorithm to generate incorrect results. We also show that the performance of the corrected algorithm can be improved by a minor adjustment in the code. [ABSTRACT FROM AUTHOR]

Focuses on several improvements to the estimation of partial derivatives in Algorithm 761. Calculation of the probability and final weights in subroutine SDPD3P; Computation of a determinant in subroutine SDLEQN; Calculation of the condition number of a matrix in subroutine SDLEQN.