There are several approaches for computing the inverse of a dense square matrix, say A, namely Gaussian elimination, block wise inversion, and LU factorization (LUF). The latter is used in mathematical software librar...
详细信息
ISBN:
(纸本)9781538632505
There are several approaches for computing the inverse of a dense square matrix, say A, namely Gaussian elimination, block wise inversion, and LU factorization (LUF). The latter is used in mathematical software libraries such as SCALAPACK, PBLAS and MATLAB. The inversion routine in SCALAPACK library (called PDGETRI) consists, once the two factors L and U are known (where A=LU), in first inverting U (PDGETRF) then solving a triangular matrix system giving A(-1). A symmetric way consists in first inverting L, then solving a matrix system giving A(-1). Alternatively, one could compute the inverses of both U and L, then their product and get A(-1). On the other hand, the Strassen fast matrix inversion algorithm is known as an efficient alternative for solving our problem. We propose in this paper a series of different versions for parallel dense matrix inversion based on the 'Divide and Conquer' paradigm. A theoretical performance study permits to establish an accurate comparison between the designed algorithms. We achieved a series of experiments that permit to validate the contribution and lead to efficient performances obtained for large matrix sizes i.e. up to 40% faster than SCALAPACK.
This paper presents a new, linear algorithm for performing the roll operation on binary trees. Based on the inorder tree traversal, this algorithm has a very simple structure and achieves linear time and space complex...
详细信息
ISBN:
(纸本)9781509038435
This paper presents a new, linear algorithm for performing the roll operation on binary trees. Based on the inorder tree traversal, this algorithm has a very simple structure and achieves linear time and space complexity. A detailed analysis of this algorithm is presented, showing how its design contributes to a more streamlined operation and an improved time complexity over the original-and only other known to the authors-binary tree roll algorithm. A practical implementation of both algorithms is benchmarked by counting the minimum and maximum numbers of basic operations, as well as measuring the minimum and maximum amounts of memory space required by the algorithms to run to completion, across all binary tree topologies with progressively increasing numbers of nodes. Results obtained from this empirical analysis quantify the best and worst-case complexities of both algorithms and show how the improved algorithm outperforms the original one asymptotically, particularly in regards to their time complexity.
A general method for the reliability evaluation of multistate networks is using minimal path vectors (d-MPs for short). Most reported works on generating d-MPs are based on minimal paths (MPs for short). Currently, al...
详细信息
ISBN:
(纸本)9781538609187
A general method for the reliability evaluation of multistate networks is using minimal path vectors (d-MPs for short). Most reported works on generating d-MPs are based on minimal paths (MPs for short). Currently, all reported MP-based algorithms generate duplicated d-MPs during the search process and additional recursive comparison is required to remove those duplications. However, the number of duplications increases substantially with the size of network. Thus, a more efficient algorithm is needed to search for all d-MPs without duplications. In this study, we proposed an improved algorithm based on the breadth-first search to search for d-MPs without duplications. The mechanism on generating duplicated d-MPs is investigated. A novel approach is incorporated into the existing algorithm to generate the d-MPs without duplications. Through computational experiments, it is found that the proposed algorithm is more efficient than existing algorithms for finding all d-MPs.
The purpose of this study is to develop a reliable machining condition monitoring system (MCMS) of end-milling for practicing engineers, which is a monitoring system with time series recursive algorithm. The suggested...
详细信息
ISBN:
(纸本)9783319509044;9783319509037
The purpose of this study is to develop a reliable machining condition monitoring system (MCMS) of end-milling for practicing engineers, which is a monitoring system with time series recursive algorithm. The suggested MCMS can analyze end-milling force signals using power spectrum analysis (PSA) and frequency response function analysis (FRFA) with recursive parametric model. Comparing with other non-parametric technique of time series, the suggested PSA and FRFA are using recursive parametric techniques. It is applied to practical application for monitoring of tooth passing which is closely related to spindle speed and chatter vibration. In order to detect several independent physical components such as tooth passing and chatter, it is presented in the frequency domain. This analysis provides an effective method in monitoring. The proposed MCMS is an efficient and reliable method for detecting spindle speed and malfunction behavior. In PSA and FRFA analysis, the recursive extended instrument variable(REIV) is used for on-line identification and mode detection in end-milling. The objective of MCMS in this work also includes a comparison of chatter and tooth passing with recursive algorithm.
Wireless spread spectrum is a standout amongst the most valuable assets. With the fast development of the quantity of remote gadgets, interchanges over the unlicensed range groups get to be extremely swarmed. Data dis...
详细信息
ISBN:
(纸本)9781509061358
Wireless spread spectrum is a standout amongst the most valuable assets. With the fast development of the quantity of remote gadgets, interchanges over the unlicensed range groups get to be extremely swarmed. Data dissemination in the wireless environment is usually characterized as the spreading of data to numerous goals through communicating. The principle target is to achieve the most extreme number of neighbors with each sent parcel. The main objective of the paper is to find the best routing and resource allocation strategies in order to minimize the average end-to-end delay of multiple data connections in the cognitive radio based wireless mesh network. Wireless mesh nodes utilize the cognitive radio to share the spectrum with primary users. Depending on the primary user's activities, the spectrum resources available to the cognitive mesh nodes are varying in both space and time. In this joint design scheme can accommodate the traffic load, or achieve half the delay compared to the disjoint methods.
In this paper, a modified and improved approach to the recently proposed multiple-resonator-based observer structure for harmonic estimation has been proposed. In the previous papers, two inherent particular cases hav...
详细信息
ISBN:
(纸本)9781538635025
In this paper, a modified and improved approach to the recently proposed multiple-resonator-based observer structure for harmonic estimation has been proposed. In the previous papers, two inherent particular cases have been considered. In the first case, estimation is performed in the point located in the middle of the observation interval, and exhibits good noises and unwanted harmonics attenuation but possesses a large response delay. In the second case, the estimation point is at the end of the observation window. In this case, the filters are able to form a zero-flat phase response about the operation frequency and hence able to provide instantaneous estimates, but with large overshoots caused by resonant frequencies at the edges of the pass band, and the high level of the sidelobs. In this paper, the estimation point is shifted along the observation interval reshaping frequency responses to tradeoff between those opposite requirements. The effectiveness of the proposed algorithm is shown through simulations.
The LU factorization (LUF) algorithm is an important kernel used in many Linear Algebra applications such as the resolution of systems of linear equations, the inversion of square matrices and the computation of matri...
详细信息
ISBN:
(纸本)9781538635810
The LU factorization (LUF) algorithm is an important kernel used in many Linear Algebra applications such as the resolution of systems of linear equations, the inversion of square matrices and the computation of matrix eigenvalues. It is also used in the LINPACK benchmark for ranking the Top 500 most powerful supercomputers. We propose in this paper a parallel recursive algorithm for LUF based on the 'Divide and Conquer' paradigm. A theoretical performance study permits to establish an accurate comparison between the designed algorithm and the PBLAS library. We achieved a series of experiments that permits to validate the contribution and lead to efficient performances obtained for large sized matrices i.e. up to 40% faster than SCALAPACK.
Different algorithms exist that can be applied to the calculation of the effects of true coincidence summing in gamma-ray spectrometry. Some of these, however, are not capable of reproducing the count rates in all the...
详细信息
Different algorithms exist that can be applied to the calculation of the effects of true coincidence summing in gamma-ray spectrometry. Some of these, however, are not capable of reproducing the count rates in all the pure sum peaks that a spectrum may contain. A recursive, easy-to-implement deterministic algorithm has been developed that overcomes this shortcoming. (c) 2011 Elsevier Ltd. All rights reserved.
This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size ...
详细信息
This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.
This paper studies a parameter estimation problem of networked linear systems with fixed-rate quantization. Under the minimum mean square error criterion, we propose a recursive estimator of stochastic approximation t...
详细信息
This paper studies a parameter estimation problem of networked linear systems with fixed-rate quantization. Under the minimum mean square error criterion, we propose a recursive estimator of stochastic approximation type, and derive a necessary and sufficient condition for its asymptotic unbiasedness. This motivates to design an adaptive quantizer for the estimator whose strong consistency, asymptotic unbiasedness, and asymptotic normality are rigorously proved. Using the Newton-based and averaging techniques, we obtain two accelerated recursive estimators with the fastest convergence speed of O(1/k), and exactly evaluate the quantization effect on the estimation accuracy. If the observation noise is Gaussian, an optimal quantizer and the accelerated estimators are co-designed to asymptotically approach the minimum Cramer-Rao lower bound. All the estimators share almost the same computational complexity as the gradient algorithms with un-quantized observations, and can be easily implemented. Finally, the theoretical results are validated by simulations. (C) 2014 Elsevier Ltd. All rights reserved.
暂无评论