Recently, recursion was introduced into the area of Dense Linear Algebra withthe intent of producing new algorithms as well as improving its existing algorithms. Recursion, via the divide-and-conquer paradigm, introd...
详细信息
data dependence analysis for automatic parallelization of sequential tree codes is discussed. Hierarchical numerical algorithms often use tree datastructures for unbalanced, adaptively and dynamically created trees. ...
详细信息
the full format datastructures of Dense Linear Algebra hurt the performance of its factorization algorithms. Full format rectangular matrices are the input and output of level the 3 BLAS. It follows that the LAPACK a...
详细信息
the proceedings contain 44 papers. the special focus in this conference is on algorithms and datastructures. the topics include: Shape segmentation and matching with flow discretization;phylogenetic reconstruction fr...
ISBN:
(纸本)3540405453
the proceedings contain 44 papers. the special focus in this conference is on algorithms and datastructures. the topics include: Shape segmentation and matching with flow discretization;phylogenetic reconstruction from gene-rearrangement data with unequal gene content;common-deadline lazy bureaucrat scheduling problems;bandwidth-constrained allocation in grid computing;algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection;fast algorithms for a class of temporal range queries;optimal worst-case operations for implicit cache-oblivious search trees;extremal configurations and levels in pseudoline arrangements;fast relative approximation of potential fields;integrated prefetching and caching with read and write requests;online seat reservations via offline seating arrangements;routing and call control algorithms for ring networks;algorithms and models for railway optimization;approximation of rectilinear Steiner trees with length restrictions on obstacles;cropping-resilient segmented multiple watermarking;on simultaneous planar graph embeddings;approximation algorithm for hotlink assignments in web directories;drawing graphs with large vertices and thick edges;semi-matchings for bipartite graphs and load balancing;sorting circular permutations by reversal;an improved bound on Boolean matrix multiplication for highly clustered data;real two dimensional scaled matching;the zigzag path of a pseudo-triangulation;improved approximation algorithms for the quality of service Steiner tree problem;a model for analyzing black-box optimization;on the hausdorff voronoi diagram of point clusters in the plane;significant-presence range queries in categorical data and parameterized complexity of directed feedback set problems in tournaments.
We describe a new data format for storing triangular and symmetric matrices called RFP (Rectangular Full Packed). the standard two dimensional arrays of Fortran and C (also known as full format) that are used to store...
详细信息
the proceedings contain 19 papers. the topics discussed include: topological representation of precontact algebras;relational semantics through duality;duality theory for projective algebras;relational approach to Boo...
详细信息
ISBN:
(纸本)3540333398
the proceedings contain 19 papers. the topics discussed include: topological representation of precontact algebras;relational semantics through duality;duality theory for projective algebras;relational approach to Boolean logic problems;static analysis of programs using omega algebra with tests;weak contact structures;on relational cycles;a framework for Kleene algebra with an embedded structure;non-termination in unifying theories of programming;towards an algebra of hybrid systems;relational correspondences for lattices with operators;control-flow semantics for assembly-level data-flow graphs;relational implementation of simple parallel evolutionary algorithms;lattice-based paraconsistent logic;verification of pushdown systems using omega algebra with domain;relational representability for algebras of substructural logics;Knuth-Bendix completion as a data structure;and time-dependent contact structures in Goguen categories.
We propose a cooperating Knuth-Bendix completion procedure for transitive relations and equivalences and apply it as a data structure for novel dynamic strongly connected component algorithms. Benefits are separation ...
详细信息
A well known strategy for handling the exponential complexity of modular discrete event systems is to represent the state space symbolically, using binary decision diagrams (BBDs). In this paper, key success factors i...
详细信息
A well known strategy for handling the exponential complexity of modular discrete event systems is to represent the state space symbolically, using binary decision diagrams (BBDs). In this paper, key success factors in the design of efficient BDD-based reachability algorithms for synthesis and verification are discussed. It is also shown how the modular structure of a discrete event system (DES) can be utilized by taking advantage of the process communication graph and partitioning techniques. A reachability algorithm based on these principles is discussed and a proof of correctness for the algorithm is given
Hierarchical interface-based supervisory control (HISC) decomposes a discrete-event system (DES) into a high-level subsystem which communicates with n ges 1 low-level subsystems, through separate interfaces which rest...
详细信息
Hierarchical interface-based supervisory control (HISC) decomposes a discrete-event system (DES) into a high-level subsystem which communicates with n ges 1 low-level subsystems, through separate interfaces which restrict the interaction of the subsystems. It provides a set of local conditions that can be used to verify global conditions such as nonblocking and controllability. the current HISC verification and synthesis algorithms are based upon explicit state and transition listings which limit the size of a given level to about 10 7 states when 1GB of memory is used. In this paper, we extend the HISC approach by introducing a set of predicate based fixed point operators that allow us to do a per level synthesis to construct for each level a maximally permissive supervisor that satisfies the corresponding HISC conditions. We prove that these fixpoint operators compute the required level-wise supremal languages. We then present algorithmsthat implement the fixpoint operators. Based on these algorithms, a symbolic implementation is briefly discussed which can be implemented using binary decision diagrams. We also discuss a method to implement our synthesized supervisors in a more compact manner. A large manufacturing system example (worst case state space on the order of 10 30 ) extended from the ALP example is briefly discussed. the example showed that we can now handle a given level with a statespace as large as 10 15 states, using less than 160MB of memory. this represents a significant improvement in the size of systems that can be handled by the HISC approach. A software tool for synthesis and verification of HISC systems using our approach was also developed
We close an open issue on dictionaries dating back to the sixthies. An array of n keys can be sorted so that searching takes 0(log n) time. Alternatively, it can be organized as a heap so that inserting and deleting k...
详细信息
ISBN:
(纸本)3540405453
We close an open issue on dictionaries dating back to the sixthies. An array of n keys can be sorted so that searching takes 0(log n) time. Alternatively, it can be organized as a heap so that inserting and deleting keys take O(log n) time. We show that these bounds can be simultaneously achieved in the worst case for searching and updating by suitably maintaining a permutation of the n keys in the array. the resulting data structure is called implicit as it uses just 0(l) extra memory cells beside the n cells for the array. the data structure is also cacheoblivious, attaining O(log(B) n) block transfers in the worst case for any (unknown) value of the block size B, without wasting any single cell of memory at any level of the memory hierarchy.
暂无评论