An efficient algorithm for linear programming

A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.

A systolic algorithm for hidden surface removal

With the advent of VLSI it has become possible to map parallel algorithms for compute-bound problems directly on silicon. Systolic architecture is very good candidate for VLSI implementation because of its regular and simple design, and regular communication pattern. In this paper, a systolic algorithm and corresponding systolic architecture, a linear systolic array, for the scanline-based hidden surface removal problem in three-dimensional computer graphics have been proposed. The algorithm is based on the concept of sample spans or intervals. The worst case time taken by the algorithm is O(n), n being the number of segments in a scanline. The time taken by the algorithm for a given scene depends on the scene itself, and on an average considerable improvement over the worst case behaviour is expected. A pipeline scheme for handling the I/O process has also been proposed which is suitable for VLSI implementation of the algorithm.

Random-Restart Reactive Tabu Search Algorithm for Detection in Large-MIMO Systems

We present a low-complexity algorithm based on reactive tabu search (RTS) for near maximum likelihood (ML) detection in large-MIMO systems. The conventional RTS algorithm achieves near-ML performance for 4-QAM in large-MIMO systems. But its performance for higher-order QAM is far from ML performance. Here, we propose a random-restart RTS (R3TS) algorithm which achieves significantly better bit error rate (BER) performance compared to that of the conventional RTS algorithm in higher-order QAM. The key idea is to run multiple tabu searches, each search starting with a random initial vector and choosing the best among the resulting solution vectors. A criterion to limit the number of searches is also proposed. Computer simulations show that the R3TS algorithm achieves almost the ML performance in 16 x 16 V-BLAST MIMO system with 16-QAM and 64-QAM at significantly less complexities than the sphere decoder. Also, in a 32 x 32 V-BLAST MIMO system, the R3TS performs close to ML lower bound within 1.6 dB for 16-QAM (128 bps/Hz), and within 2.4 dB for 64-QAM (192 bps/Hz) at 10(-3) BER.

An efficient marching algorithm for waterhammer analysis by the method of characteristics

A new fast and efficient marching algorithm is introduced to solve the basic quasilinear, hyperbolic partial differential equations describing unsteady, flow in conduits by the method of characteristics. The details of the marching method are presented with an illustration of the waterhammer problem in a simple piping system both for friction and frictionless cases. It is shown that for the same accuracy the new marching method requires fewer computational steps, less computer memory and time.

An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.

Focal plane analysis of the Knox-Thompson algorithm in speckle interferometry

For the specific case of binary stars, this paper presents signal-to-noise ratio (SNR) calculations for the detection of the parity (the side of the brighter component) of the binary using the double correlation method. This double correlation method is a focal plane version of the well-known Knox-Thompson method used in speckle interferometry. It is shown that SNR for parity detection using double correlation depends linearly on binary separation. This new result was entirely missed by previous analytical calculations dealing with a point source. It is concluded that, for magnitudes relevant to the present day speckle interferometry and for binary separations close to the diffraction limit, speckle masking has better SNR for parity detection.

Myoblast Sheet Transplantation for Treatment of Heart Failure after Myocardial Infarction

Heart failure is a common, severe, and progressive condition associated with high mortality and morbidity. Because of population-aging in the coming decades, heart failure is estimated to reach epidemic proportions. Current medical and surgical treatments have reduced mortality, but the prognosis for patients has remained poor. Transplantation of skeletal myoblasts has raised hope of regenerating the failing heart and compensating for lost cardiac contractile tissue. In the present work, we studied epicardial transplantation of tissue-engineered myoblast sheets for treatment of heart failure. We employed a rat model of myocardial infarction-induced acute and chronic heart failure by left anterior descending coronary artery ligation. We then transplanted myoblast sheets genetically modified to resist cell death after transplantation by expressing antiapoptotic gene bcl2. In addition, we evaluated the regenerative capacity of myoblast sheets expressing the cardioprotective cytokine hepatocyte growth factor in a rat chronic heart failure model. Furthermore, we utilized in vitro cardiomyocyte and endothelial cell culture models as well as microarray gene expression analysis to elucidate molecular mechanisms mediating the therapeutic effects of myoblast sheet transplantation. Our results demonstrate that Bcl2-expression prolonged myoblast sheet survival in rat hearts after transplantation and induced secretion of cardioprotective, proangiogenic cytokines. After acute myocardial infarction, these sheets attenuated left ventricular dysfunction and myocardial damage, and they induced therapeutic angiogenesis. In the chronic heart failure model, inhibition of graft apoptosis by Bcl-2 improved cardiac function, supported survival of cardiomyocytes in the infarcted area, and induced angiogenesis in a vascular endothelial growth factor receptor 1- and 2-dependent mechanism. Hepatocyte growth factor-secreting myoblast sheets further enhanced the angiogenic efficacy of myoblast sheet therapy. Moreover, myoblast-secreted paracrine factors protected cardiomyocytes against oxidative stress in an epidermal growth factor receptor- and c-Met dependent manner. This protection was associated with induction of antioxidative genes and activation of the unfolded protein response. Our results provide evidence that inhibiting myoblast sheet apoptosis can enhance the sheets efficacy for treating heart failure after acute and chronic myocardial infarction. Furthermore, we show that myoblast sheets can serve as vehicles for delivery of growth factors, and induce therapeutic angiogenesis in the chronically ischemic heart. Finally, myoblasts induce, in a paracine manner, a cardiomyocyte-protective response against oxidative stress. Our study elucidates novel mechanisms of myoblast transplantation therapy, and suggests effective means to improve this therapy for the benefit of the heart failure patient.

A near-optimal initial seed value selection in K-means means algorithm using a genetic algorithm

The K-means algorithm for clustering is very much dependent on the initial seed values. We use a genetic algorithm to find a near-optimal partitioning of the given data set by selecting proper initial seed values in the K-means algorithm. Results obtained are very encouraging and in most of the cases, on data sets having well separated clusters, the proposed scheme reached a global minimum.

A Parallel Progressive Refinement Image Rendering Algorithm on a Scalable Multithreaded VLSI Processor Array

In this paper we develop a multithreaded VLSI processor linear array architecture to render complex environments based on the radiosity approach. The processing elements are identical and multithreaded. They work in Single Program Multiple Data (SPMD) mode. A new algorithm to do the radiosity computations based on the progressive refinement approach[2] is proposed. Simulation results indicate that the architecture is latency tolerant and scalable. It is shown that a linear array of 128 uni-threaded processing elements sustains a throughput close to 0.4 million patches/sec.

Casting and heat treatment variables of Al–7Si–Mg alloy

A review of the research work that has been carried out thus far relating the casting and heat treatment variables to the structure and mechanical properties of Al–7Si–Mg (wt-%) is presented here. Although specifications recommend a wide range of magnesium contents and a fairly high content of iron, a narrow range of magnesium contents, closer to either the upper or lower specified limits depending on the properties desired, and a low iron content will have to be maintained to obtain optimum and consistent mechanical properties. A few studies have revealed that the modification of eutectic silicon slightly increases ductility and fracture toughness and also that the effect of modification is predominant at low iron content. Generally, higher solidification rates give superior mechanical properties. Delayed aging (the time elapsed between quenching and artificial aging during precipitation hardening) severely affects the strength of the alloy. The mechanism of delayed aging can be explained on the basis of Pashley's kinetic model. It has been reported that certain trace additions (cadmium, indium, tin, etc.) neutralise the detrimental effect of delayed aging. In particular, it should be noted that delayed aging is not mentioned in any of the specifications. With reference to the mechanism by which trace additions neutralise the detrimental effect of delayed aging, various hypotheses have been postulated, of which impurity–vacancy interaction appears to be the most widely accepted.

Role of lipid peroxidation in impairment of mitochondrial function at complex I by methyl isocyanate treatment of rats in vivo

The subcutaneous administration of methyl isocyanate (MIC) in 1.0 LD50 dose in rats caused a significant effect on hepatic mitochondrial function only at complex I region of the respiratory chain. MIC administration at 1.0 LD50 dose also resulted in significant increases in malondialdehyde and ferrous ion concentration in liver mitochondria. It is suggested that the augmented lipid peroxidation in hepatic mitochondria, catalyzed by iron, possibly mobilized from intracellular stores leads to the inhibition of enzymes of mitochondrial respiration at complex I region, in vivo, in rats receiving a lethal dose of MIC subcutaneously.

Studies on Compact Discharge Plasma Source for NOX Treatment in Engine Exhaust

This paper proposes a compact electric discharge plasma source for controlling NOX emission in diesel engine exhaust. An automobile ignition coil was used to generate the high voltage pulse using flyback topology. This design is aimed at retrofitting the existing catalytic converters with pulse assisted cleaning technique. In this paper we bring out a relative comparison of discharge plasma and plasma-adsorbent process at different gas flow rates. Activated alumina was used as adsorbent. The main emphasis is laid on the development of a compact pulse source from a DC supply for the removal of NOX from the filtered diesel engine exhaust.

Concise row-pruning algorithm to invert a matrix

Presented here, in a vector formulation, is an O(mn2) direct concise algorithm that prunes/identifies the linearly dependent (ld) rows of an arbitrary m X n matrix A and computes its reflexive type minimum norm inverse A(mr)-, which will be the true inverse A-1 if A is nonsingular and the Moore-Penrose inverse A+ if A is full row-rank. The algorithm, without any additional computation, produces the projection operator P = (I - A(mr)- A) that provides a means to compute any of the solutions of the consistent linear equation Ax = b since the general solution may be expressed as x = A(mr)+b + Pz, where z is an arbitrary vector. The rank r of A will also be produced in the process. Some of the salient features of this algorithm are that (i) the algorithm is concise, (ii) the minimum norm least squares solution for consistent/inconsistent equations is readily computable when A is full row-rank (else, a minimum norm solution for consistent equations is obtainable), (iii) the algorithm identifies ld rows, if any, and reduces concerned computation and improves accuracy of the result, (iv) error-bounds for the inverse as well as the solution x for Ax = b are readily computable, (v) error-free computation of the inverse, solution vector, rank, and projection operator and its inherent parallel implementation are straightforward, (vi) it is suitable for vector (pipeline) machines, and (vii) the inverse produced by the algorithm can be used to solve under-/overdetermined linear systems.