By the use of wavelet basis functions, an integral equation can be converted into a sparse matrix equation after discretization. Through the exploitation of the sparsity of the impedance matrix;the complexity of solvi...
详细信息
By the use of wavelet basis functions, an integral equation can be converted into a sparse matrix equation after discretization. Through the exploitation of the sparsity of the impedance matrix;the complexity of solving the resultant matrix equation can be greatly reduced. It has beet reported that the number of nonzero elements in a wavelet impedance matrix is alpha N-2 (0 less than or equal to alpha less than or equal to 1), where a is approximately a constant. This implies that solving the sparse matrix equation produced by a wavelet expansion has the same complexity as solving a full matrix In this Letter, however, we present an example of the wavelet impedance matrix that results in a much lower complexity-O(N). (C) 1997 John Wiley & Sons, Inc.
The importance of the meso-scale analysis of concrete has been a controversial topic. The accuracy and efficiency of numerical modelling directly influence the results and computational cost. In this study, we propose...
详细信息
The importance of the meso-scale analysis of concrete has been a controversial topic. The accuracy and efficiency of numerical modelling directly influence the results and computational cost. In this study, we propose a versatile fractal-geometry-based modelling method that can generate an aggregate model with a known gradation curve. Two numerical meso-model groups generated by the random fractal method are measured and analysed considering the gradation curve, coarse aggregate content, and fractal dimension as evaluation indices. It is verified that the evaluation indices of the numerical models are consistent with the actual ones. Based on sampling statistical analysis, the geometrical homogenization of the meso-model generated by the random fractal method is found to be satisfactory for meso-scale applications. Furthermore, the random fractal method is shown to have low algorithm complexity. (C) 2017 Elsevier B.V. All rights reserved.
This paper considers an economic lot sizing model with constant capacity, non-increasing setup cost and convex inventory cost function algorithms with computational time of O(N x TD(N))have been developed for solving ...
详细信息
This paper considers an economic lot sizing model with constant capacity, non-increasing setup cost and convex inventory cost function algorithms with computational time of O(N x TD(N))have been developed for solving the model, where N is the number of planning periods and TD(N) is the total demand This study partially characterizes the optimal planning structure of the model A new efficient algorithm with computational time of O(N log N) has also been developed based on the partial optimal structure Moreover computational study demonstrates that the new algorithm is efficient (C) 2010 Elsevier Ltd All rights reserved
This paper describes a new formulation of the problem of object recognition under a bounded-error noise model and an object recognition methodology called PERFORM that finds matches by establishing correspondences bet...
详细信息
This paper describes a new formulation of the problem of object recognition under a bounded-error noise model and an object recognition methodology called PERFORM that finds matches by establishing correspondences between model and image features using this formulation. PERFORM evaluates correspondences by intersecting error regions in the image space. The algorithm is analyzed with respect to theoretical complexity as well as actual running times. When a single solution to the matching problem is sought, the time complexity of the sequential matching algorithm for 2D-2D matching using point features is of the order O(l(3) N-2), where N is the number of model features and I is the number of image features. When line features are used, the sequential complexity is of the order O(l(2) N-2). When a single solution is sought, PERFORM runs faster than the fastest known algorithm [8] to solve the bounded-error matching problem. The PERFORM method, which was developed with parallelizability as an important requirement, is shown to be easily realizable on both SIMD and MIMD architectures. The parallel versions of PERFORM are scalable, achieving linear speedups on both the MasPar and the KSR machines. When implemented in parallel, PERFORM does not require a targe number of processors or memory, needs minimal to no inter-processor communication, requires no load balancing, and can produce all or just one solution to the matching problem. The communication-efficient version of PERFORM described in this paper has minimal memory requirements, since it only needs to store the model and image features and computes everything else on the fly.
In this paper we present a new method for the efficient implementation of the fast transversal filter (FTF) algorithm. Reduction of the arithmetic complexity is obtained by making use of the redundancy in the successi...
详细信息
In this paper we present a new method for the efficient implementation of the fast transversal filter (FTF) algorithm. Reduction of the arithmetic complexity is obtained by making use of the redundancy in the successive computations of the forward prediction error and the filtering error in the joint process. The resulting algorithm is exactly equivalent to the original FTF algorithm, hence retaining the same theoretical convergence characteristics and offering the least squares (LS) estimate at each recursion step without delay. Furthermore, the algorithm can be numerically stabilized by using a simple and effective stabilization measure which needs only one additional multiplication per recursion step. The equivalence of the proposed algorithm to the original FTF algorithm is demonstrated by simulations of an acoustic room impulse response identification.
Third generation mobile radio systems will employ TD-CDMA in their TDD mode. In a TD-CDMA mobile radio system, joint-detection is equivalent to solving a least squares problem with a system matrix that exhibits some f...
详细信息
Third generation mobile radio systems will employ TD-CDMA in their TDD mode. In a TD-CDMA mobile radio system, joint-detection is equivalent to solving a least squares problem with a system matrix that exhibits some form of block-Toeplitz structure. This structure can be successfully exploited by using variations of the Schur algorithm for computing the QR decomposition of this system matrix. Together with a displacement representation, the Schur algorithm can be straightforwardly adapted to a wide variety of matrix structures. In this paper we show this approach for two concrete manifestations of the TD-CDMA system matrix: first for a very compact, block-Toeplitz structure;and second for the less favorable Toeplitz-block structure that arises when decision feedback is added to the data process.
Antonopoulou & Papastavridis (1987) published an algorithm for computing the reliability of a circular consecutive-k-out-of-n:F system which claimed O(k . n) time. Wu & Chen (1993) correctly pointed out the al...
详细信息
Antonopoulou & Papastavridis (1987) published an algorithm for computing the reliability of a circular consecutive-k-out-of-n:F system which claimed O(k . n) time. Wu & Chen (1993) correctly pointed out the algorithm achieved only O(k . n2) time. This paper shows that the algorithm can be implemented for O(k . n) time.
papers [1] and [2] propose algorithms for testing whether the choice function induced by a (strict) preference list of length N over a universe U is substitutable. The running time of these algorithms is O (vertical b...
详细信息
papers [1] and [2] propose algorithms for testing whether the choice function induced by a (strict) preference list of length N over a universe U is substitutable. The running time of these algorithms is O (vertical bar U vertical bar(3).N-3), respectively O (vertical bar U vertical bar(2).N-3). In this note we present an algorithm with running time O (vertical bar U vertical bar(2).N-2). Note that N may be exponential in the size DUI of the universe. (C) 2018 Elsevier B.V. All rights reserved.
In the gas station problem we want to find the cheapest path between two vertices of an n-vertex graph. Our car has a specific fuel capacity and at each vertex we can fill our car with gas, with the fuel cost dependin...
详细信息
In the gas station problem we want to find the cheapest path between two vertices of an n-vertex graph. Our car has a specific fuel capacity and at each vertex we can fill our car with gas, with the fuel cost depending on the vertex. Furthermore, we are allowed at most Delta stops for refuelling. In this short paper we provide an algorithm solving the problem in O (Delta n(2) + n(2) logn) steps improving an earlier result by Khuller, Malekian and Mestre. (C) 2017 Elsevier B.V. All rights reserved.
作者：
BONNET, MMACCHI, OCNRS
ECOLE SUPER ELECTSIGNAUX & SYST LABF-91190 GIF SUR YVETTEFRANCE
AnalyseDeux algorithmes pour annuleur d’écho par filtrage adaptatif sont comparés à l’aide de plusieurs paramètres : résidu d’écho, complexité des calculs en précision finie ...
详细信息
Analyse
Deux algorithmes pour annuleur d’écho par filtrage adaptatif sont comparés à l’aide de plusieurs paramètres : résidu d’écho, complexité des calculs en précision finie et vitesse de convergence. Il s’agit de l’algorithme classique du gradient et de l’un de ses dérivés : l’algorithme du signe de l’erreur. Les auteurs montrent qu’en utilisant un bruit auxiliaire contrôlé, l’algorithme du signe a un comportement semblable à celui de l’algorithme du gradient en ce qui concerne le résidu d’écho et la longueur des mots binaires. Il est nettement supérieur à l’algorithme du gradient en ce qui concerne la complexité globale. Le problème de la vitesse de convergence plus faible peut être résolu par des techniques simples d’initialisation. Des simulations illustrent les résultats théoriques.
暂无评论