QRT: A Qr-based tridiagonalization algorithm for nonsymmetric matrices

The stable similarity reduction of a nonsymmetric square matrix to tridiagonal form has been a long-standing problem in numerical linear algebra. The biorthogonal Lanczos process is in principle a candidate method for this task, but in practice it is confined to sparse matrices and is restarted periodically because roundoff errors affect its three-term recurrence scheme and degrade the biorthogonality after a few steps. This adds to its vulnerability to serious breakdowns or near-breakdowns, the handling of which involves recovery strategies such as the look-ahead technique, which needs a careful implementation to produce a block-tridiagonal form with unpredictable block sizes. Other candidate methods, geared generally towards full matrices, rely on elementary similarity transformations that are prone to numerical instabilities. Such concomitant difficulties have hampered finding a satisfactory solution to the problem for either sparse or full matrices. This study focuses primarily on full matrices. After outlining earlier tridiagonalization algorithms from within a general framework, we present a new elimination technique combining orthogonal similarity transformations that are stable. We also discuss heuristics to circumvent breakdowns. Applications of this study include eigenvalue calculation and the approximation of matrix functions.

Summarizing level-two topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

Multiscale histograms: Summarizing topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this paper, we present several novel techniques to eectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important topological relations: contains, contained, overlap, and disjoint. We rst present a novel framework to construct a multiscale histogram composed of multiple Euler histograms with the guarantee of the exact summarization results for aligned windows in constant time. Then we present an approximate algorithm, with the approximate ratio 19/12, to minimize the storage spaces of such multiscale Euler histograms, although the problem is generally NP-hard. To conform to a limited storage space where only k Euler histograms are allowed, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy. Finally, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. Our extensive experiments against both synthetic and real world datasets demonstrated that the approximate mul- tiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost effciency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for the real datasets.

Functionally partitioned module-based programmable architecture for wireless base-band processing

A specialised reconfigurable architecture is targeted at wireless base-band processing. It is built to cater for multiple wireless standards. It has lower power consumption than the processor-based solution. It can be scaled to run in parallel for processing multiple channels. Test resources are embedded on the architecture and testing strategies are included. This architecture is functionally partitioned according to the common operations found in wireless standards, such as CRC error correction, convolution and interleaving. These modules are linked via Virtual Wire Hardware modules and route-through switch matrices. Data can be processed in any order through this interconnect structure. Virtual Wire ensures the same flexibility as normal interconnects, but the area occupied and the number of switches needed is reduced. The testing algorithm scans all possible paths within the interconnection network exhaustively and searches for faults in the processing modules. The testing algorithm starts by scanning the externally addressable memory space and testing the master controller. The controller then tests every switch in the route-through switch matrix by making loops from the shared memory to each of the switches. The local switch matrix is also tested in the same way. Next the local memory is scanned. Finally, pre-defined test vectors are loaded into local memory to check the processing modules. This paper compares various base-band processing solutions. It describes the proposed platform and its implementation. It outlines the test resources and algorithm. It concludes with the mapping of Bluetooth and GSM base-band onto the platform.

High-pressure adsorption of supercritical gases on activated carbons: An improved approach based on the density functional theory and the bender equation of state

Adsorption of nitrogen, argon, methane, and carbon dioxide on activated carbon Norit R1 over a wide range of pressure (up to 50 MPa) at temperatures from 298 to 343 K (supercritical conditions) is analyzed by means of the density functional theory modified by incorporating the Bender equation of state, which describes the bulk phase properties with very high accuracy. It has allowed us to precisely describe the experimental data of carbon dioxide adsorption slightly above and below its critical temperatures. The pore size distribution (PSD) obtained with supercritical gases at ambient temperatures compares reasonably well with the PSD obtained with subcritical nitrogen at 77 K. Our approach does not require the skeletal density of activated carbon from helium adsorption measurements to calculate excess adsorption. Instead, this density is treated as a fitting parameter, and in all cases its values are found to fall into a very narrow range close to 2000 kg/m(3). It was shown that in the case of high-pressure adsorption of supercritical gases the PSD could be reliably obtained for the range of pore width between 0.6 and 3 run. All wider pores can be reliably characterized only in terms of surface area as their corresponding excess local isotherms are the same over a practical range of pressure.

Speeding up the EM algorithm for mixture model-based segmentation of magnetic resonance images

Mixture models implemented via the expectation-maximization (EM) algorithm are being increasingly used in a wide range of problems in pattern recognition such as image segmentation. However, the EM algorithm requires considerable computational time in its application to huge data sets such as a three-dimensional magnetic resonance (MR) image of over 10 million voxels. Recently, it was shown that a sparse, incremental version of the EM algorithm could improve its rate of convergence. In this paper, we show how this modified EM algorithm can be speeded up further by adopting a multiresolution kd-tree structure in performing the E-step. The proposed algorithm outperforms some other variants of the EM algorithm for segmenting MR images of the human brain. (C) 2004 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

Genetic algorithm-based spinning reserve dispatching in a competitive electricity market

Power systems rely greatly on ancillary services in maintaining operation security. As one of the most important ancillary services, spinning reserve must be provided effectively in the deregulated market environment. This paper focuses on the design of an integrated market for both electricity and spinning reserve service with particular emphasis on coordinated dispatch of bulk power and spinning reserve services. A new market dispatching mechanism has been developed to minimize the ISO's total payment while ensuring system security. Genetic algorithms are used in the finding of the global optimal solutions for this dispatching problem. Case studies and corresponding analyses haw been carried out to demonstrate and discuss the efficiency and usefulness of the proposed market.

Population-based continuous optimization, probabilistic modelling and mean shift

Evolutionary algorithms perform optimization using a population of sample solution points. An interesting development has been to view population-based optimization as the process of evolving an explicit, probabilistic model of the search space. This paper investigates a formal basis for continuous, population-based optimization in terms of a stochastic gradient descent on the Kullback-Leibler divergence between the model probability density and the objective function, represented as an unknown density of assumed form. This leads to an update rule that is related and compared with previous theoretical work, a continuous version of the population-based incremental learning algorithm, and the generalized mean shift clustering framework. Experimental results are presented that demonstrate the dynamics of the new algorithm on a set of simple test problems.

The effect of an algorithm-based sedation guideline on the duration of mechanical ventilation in an Australian intensive care unit

To examine the effect of an algorithm-based sedation guideline developed in a North American intensive care unit (ICU) on the duration of mechanical ventilation of patients in an Australian ICU. The intervention was tested in a pre-intervention, post-intervention comparative investigation in a 14-bed adult intensive care unit. Adult mechanically ventilated patients were selected consecutively (n =322) The pre-intervention and post-intervention groups were similar except for a higher number of patients with a neurological diagnosis in the pre-intervention group. An algorithm-based sedation guideline including a sedation scale was introduced using a multifaceted implementation strategy. The median duration of ventilation was 5.6 days in the post-intervention group, compared with 4.8 days for the pre-intervention group (P = 0.99). The length of stay was 8.2 days in the post-intervention group versus 7.1 days in the pre-intervention group (P = 0.04). There were no statistically significant differences for the other secondary outcomes, including the score on the Experience of Treatment in ICU 7 item questionnaire, number of tracheostomies and number of self-extubations. Records of compliance to recording the sedation score during both phases revealed that patients were slightly more deeply sedated when the guideline was used. The use of the algorithm-based sedation guideline did not reduce duration of mechanical ventilation in the setting of this study.

Seizure detection algorithm for neonates based on wave-sequence analysis

Objective: The description and evaluation of the performance of a new real-time seizure detection algorithm in the newborn infant. Methods: The algorithm includes parallel fragmentation of EEG signal into waves; wave-feature extraction and averaging; elementary, preliminary and final detection. The algorithm detects EEG waves with heightened regularity, using wave intervals, amplitudes and shapes. The performance of the algorithm was assessed with the use of event-based and liberal and conservative time-based approaches and compared with the performance of Gotman's and Liu's algorithms. Results: The algorithm was assessed on multi-channel EEG records of 55 neonates including 17 with seizures. The algorithm showed sensitivities ranging 83-95% with positive predictive values (PPV) 48-77%. There were 2.0 false positive detections per hour. In comparison, Gotman's algorithm (with 30 s gap-closing procedure) displayed sensitivities of 45-88% and PPV 29-56%; with 7.4 false positives per hour and Liu's algorithm displayed sensitivities of 96-99%, and PPV 10-25%; with 15.7 false positives per hour. Conclusions: The wave-sequence analysis based algorithm displayed higher sensitivity, higher PPV and a substantially lower level of false positives than two previously published algorithms. Significance: The proposed algorithm provides a basis for major improvements in neonatal seizure detection and monitoring. Published by Elsevier Ireland Ltd. on behalf of International Federation of Clinical Neurophysiology.

Structure of saccharose-based carbon and transport of confined fluids: hybrid reverse Monte Carlo reconstruction and simulation studies

We present results of the reconstruction of a saccharose-based activated carbon (CS1000a) using hybrid reverse Monte Carlo (HRMC) simulation, recently proposed by Opletal et al. [1]. Interaction between carbon atoms in the simulation is modeled by an environment dependent interaction potential (EDIP) [2,3]. The reconstructed structure shows predominance of sp(2) over sp bonding, while a significant proportion of sp(3) hybrid bonding is also observed. We also calculated a ring distribution and geometrical pore size distribution of the model developed. The latter is compared with that obtained from argon adsorption at 87 K using our recently proposed characterization procedure [4], the finite wall thickness (FWT) model. Further, we determine self-diffusivities of argon and nitrogen in the constructed carbon as functions of loading. It is found that while there is a maximum in the diffusivity with respect to loading, as previously observed by Pikunic et al. [5], diffusivities in the present work are 10 times larger than those obtained in the prior work, consistent with the larger pore size as well as higher porosity of the activated saccharose carbon studied here.

Investigating the performance analysis of EASI algorithm and EKENS algorithm in nonlinear model

This paper investigates the performance of EASI algorithm and the proposed EKENS algorithm for linear and nonlinear mixtures. The proposed EKENS algorithm is based on the modified equivariant algorithm and kernel density estimation. Theory and characteristic of both the algorithms are discussed for blind source separation model. The separation structure of nonlinear mixtures is based on a nonlinear stage followed by a linear stage. Simulations with artificial and natural data demonstrate the feasibility and good performance of the proposed EKENS algorithm.