Narrow Results

In this paper, we consider the problem of solving sparse linear systems occurring in finite difference applications (or N × N grid problems, N being the size of the linear system). We propose a new algorithm for the problem which is based on the Cholesky factorization, a symmetric variant of Gaussian elimination tailored to symmetric positive definite systems. The algorithm employs a new technique called bidirectional factorization to produce the complete solution vector by solving only one triangular system against two triangular systems in the existing Cholesky factorization after the factorization phase. The effectiveness of the new algorithm is demonstrated by comparing its performance with that of the existing Cholesky factorization for solving regular finite difference grid problems on hypercube multiprocessors.

This paper presents an integrated approach to two issues relevant to efficient parallel sparse Cholesky factorization: 1) matrix reordering for parallelism, and, 2) mapping of data to processors. A clustering heuristic is proposed to performs a fill-preserving reordering and mapping of data onto a fixed number of processors. Performance results on a Cray T3D are presented to demonstrate its effectiveness.

In the last couple of years, quantum computing has come out as emerging trends of computation not only due to its immense popularity but also for its commitment towards physical realization of quantum circuit in on-chip units. At the same time, the process of physical realization has faced several design constraints and one such problem is nearest neighbor (NN) enforcement which demands all the operating qubits to be placed adjacent in the implementable circuit. Though SWAP gate embedment can transform a design into NN architecture, it still creates overhead in the design. So, designing algorithms to restrict the use of SWAPs bears high importance.

Considering this fact, in this work, we are proposing a heuristic-based improved qubit placement strategy for efficient implementation of NN circuit. Two different design policies are being developed here. In the first scheme, a global reordering technique based on clustering approach is shown. In the second scheme, a local reordering technique based on look-ahead policy is developed. This look-ahead strategy considers the impact over the gates in the circuit and thereby estimates the effect using a cost metric to decide the suitable option for SWAP implementation. Furthermore, the joint use of both the ordering schemes also has been explored here. To ascertain the correctness of our design algorithms, we have tested them over a wide range of benchmarks and the obtained results are compared with some state-of-the-art design approaches. From this comparison, we have witnessed a considerable reduction on SWAP cost in our design scheme against the reported works’ results.

We describe a syntactic transformation model based on the probabilistic context-free grammar. This model is trained by using bilingual corpus and a broad coverage parser of the source language. Then we present two methods to solve the word-order problem using the transformational model. The first method deals with this problem in the preprocessing phase. There is no reordering in the decoding phase. The second method employs the syntactic transformation model in the decoding phase for phrase reordering within chunks. Speed is an advantage of this method. We considered translation from English to Vietnamese and from English to French. Our experiments showed significant BLEU-score improvements in comparison with Pharaoh, a state-of-the-art phrase-based SMT system.

In phrase-based, statistical machine translation systems, variations in grammatical structures between source and target languages can cause large movements of phrases. Modelling such movements is crucial in achieving translations of long reorderings that appear natural in the target language. In this paper, we explore generative and discriminative learning approaches to phrase reordering in Arabic to English. Formulating the reordering problem as a classification problem and using naive Bayes, we achieve an improvement in BLEU score over a lexicalised reordering model for Arabic-English. The model is scalable to large datasets.