106 results
Search Results
2. Real representation for solving reduced biquaternion matrix equations XF−AX=BY$$ XF- AX= BY $$ and XF−AX˜=BY$$ XF-A\tilde{X}= BY $$.
- Author
-
Ding, Wenxv, Li, Ying, and Wei, Anli
- Subjects
- *
EQUATIONS , *MATRICES (Mathematics) , *QUATERNION functions , *ALGORITHMS - Abstract
In this paper, a new real representation of reduced biquaternion matrix is proposed, and the solutions of the reduced biquaternion matrix equations XF−AX=BY$$ XF- AX= BY $$ and XF−AX˜=BY$$ XF-A\tilde{X}= BY $$ are solved by means of this method. The corresponding numerical algorithm is provided, and the effectiveness of this method is verified by numerical examples. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
3. Component‐based nearest neighbour subspace clustering.
- Author
-
Hotta, Katsuya, Xie, Haoran, and Zhang, Chao
- Subjects
- *
NEIGHBORS , *MATRICES (Mathematics) , *ALGORITHMS , *HYPOTHESIS - Abstract
In this paper, the problem of clustering data points that lie near or on a union of independent low‐dimensional subspaces is addressed. To this end, the popular spectral clustering‐based algorithms usually follow a two‐stage strategy that initially builds an affinity matrix and then applies spectral clustering. However, an inappropriate affinity matrix that does not sufficiently connect data points lying on the same subspace will easily lead to the issue of over‐segmentation. To alleviate this issue, building the affinity matrix based on subspace hypotheses generated by an iterative sampling operation according to the Random Cluster Model under the framework of energy minimisation is proposed. Specifically, each hypothesis is generated from a large number of data points by sampling a component in a K‐nearest neighbour graph. Extensive experiments on synthetic data and real‐world datasets show that the proposed method can improve the connectivity of the affinity matrix and provide competitive results against state‐of‐the‐art methods. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
4. Low latency group‐sorted QR decomposition algorithm for larger‐scale MIMO systems.
- Author
-
Chen, Lirui, Wang, Yu, Xing, Zuocheng, Qiu, Shikai, Wang, Qinglin, and Li, Yongzhong
- Subjects
- *
MIMO systems , *WIRELESS communications , *DETECTORS , *ALGORITHMS , *MATRICES (Mathematics) - Abstract
Sorted QR decomposition (SQRD) has been extensively adopted for various multiple‐input‐multiple‐output (MIMO) detectors, in which the sorting process incurs severe latency when it comes to larger‐scale MIMO situations. This paper proposes a group‐SQRD (GSQRD) algorithm to alleviate the latency problem of general SQRD architectures for larger‐scale MIMO systems. Via predictively sorting a group of 4 columns at one stage, the GSQRD could eliminate the processing latency by 41% for decomposing 16×16 complex‐valued matrices. Additionally, this percentage even rises up to 68% for decomposing 128×128 matrices. To analyse the side effects, the GSQRD is applied in various MIMO detectors in a simulation link, which exhibits a negligible performance degradation for MIMO detection. Moreover, GSQRD is a hardware‐friendly algorithm because the division and square root operations in GSQRD are converted to multiplications for simplifying the hardware implementation. Based on this algorithm, two corresponding hardware architectures, which contains 2 and 4 columns respectively in a sorting group, are also implemented with 65‐nm CMOS technology. These architectures can work at 513 MHz to decompose 16×16 complex‐valued matrices. The processing latencies are respectively 0.32 and 0.26 μs, superior to the state‐of‐art designs. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. Shrunk multiline addressing method in a passive-matrix-driven liquid powder display.
- Author
-
Asakawa, Miehihiro, Kaneko, Sadayuki, and Hattori, Reiji
- Subjects
- *
DISPLAY systems , *ALGORITHMS , *IMAGE , *MATRICES (Mathematics) , *QUALITY - Abstract
The article presents a study which explained shrunk multiline addressing method (SMLA) in a passive-matrix driven liquid powder display. The researchers devised an algorithm to collect SMLA data that quickly reduces the number of scanning lines. The update time is said to be reduced by 44.5% and remained the same regardless of the increase in image size. Results confirmed reduction in the update time with the same image quality as that of the conventional ones.
- Published
- 2011
- Full Text
- View/download PDF
6. A matrix rational Lanczos method for model reduction in large-scale first- and second-order dynamical systems.
- Author
-
Barkouki, H., Bentbib, A.H., and Jbilou, K.
- Subjects
- *
LANCZOS method , *KRYLOFF-Bogoliuboff method , *DYNAMICAL systems , *MATRICES (Mathematics) , *ALGORITHMS - Abstract
In the present paper, we describe an adaptive modified rational global Lanczos algorithm for model-order reduction problems using multipoint moment matching-based methods. The major problem of these methods is the selection of some interpolation points. We first propose a modified rational global Lanczos process and then we derive Lanczos-like equations for the global case. Next, we propose adaptive techniques for choosing the interpolation points. Second-order dynamical systems are also considered in this paper, and the adaptive modified rational global Lanczos algorithm is applied to an equivalent state space model. Finally, some numerical examples will be given. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
7. Processing technique of ratings for ranking of alternatives (PROTERRA).
- Author
-
Kobryń, Andrzej and Prystrom, Joanna
- Subjects
- *
MULTIPLE criteria decision making , *MATRICES (Mathematics) , *ANALYTIC hierarchy process , *EVALUATION methodology , *ALGORITHMS - Abstract
Abstract: This paper presents a new approach to multicriteria decision analysis. They were named as processing technique of ratings for ranking of alternatives (PROTERRA). The consecutive steps of the process include normalization of the ratings, calculating of the ratings ratios within each pair of the alternatives, creating a component matrix for each of the criteria, and creating a total matrix that is the sum of the weighted component matrices. Aggregated ratings of individual alternatives result from the sums of all the values of the corresponding rows and columns of the total matrix elements. A practical application of the PROTERRA has been illustrated with an example of a decision problem concerning the choice of a shopping centre location. The analysis results of the PROTERRA are compared with other results obtained using the most popular methods, that is, analytic hierarchy process, preference ranking organization method for enrichment of evaluations, and technique for order performance by similarity to ideal solution. In order to assess the stability of the ranking order obtained by the PROTERRA algorithm, the influence of weights variations on the final ranking results were tested. The sensitivity analysis was also carried out for the other methods, that is, preference ranking organization method for enrichment of evaluations, analytic hierarchy process, and technique for order performance by similarity to ideal solution. On this basis, a stability of rankings resulting from all analysed methods were compared. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
8. The multidimensional nD‐GRAS method: Applications for the projection of multiregional input–output frameworks and valuation matrices.
- Author
-
Valderas‐Jaramillo, Juan Manuel and Rueda‐Cantuche, José Manuel
- Subjects
- *
VALUATION , *MATRICES (Mathematics) , *INPUT-output analysis , *ALGORITHMS , *ANALYTICAL solutions - Abstract
We present a multidimensional generalization of the GRAS method (nD‐GRAS) for the estimation of multiple matrices in an integrated framework. The potential applications of this method in regional and multi‐regional input–output analyses based on national/regional accounts frameworks are many. We provide two real applications, a 3D‐GRAS that estimates a use table at basic prices jointly with valuation matrices for Denmark; and a 4D‐GRAS for estimating intercountry input–output tables with OECD data. We show that higher dimensional GRAS methods provide more consistent and accurate estimates than those with lower number of dimensions. We provide the analytical closed‐form solution and the RAS‐like algorithm for an easy operationalization. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
9. Numerical analysis of electrical logging-while-drilling tool using propagator matrix method.
- Author
-
Liu, Guo‐Sheng and Yang, Hai‐Dong
- Subjects
- *
ELECTRIC logging , *NUMERICAL analysis , *MATRICES (Mathematics) , *MAXWELL equations , *ANISOTROPY , *ALGORITHMS , *INHOMOGENEOUS materials , *COMPUTER simulation - Abstract
SUMMARY In this paper, a propagator matrix method applied to logging-while-drilling tools is introduced and extended to deal with the anisotropic and radially inhomogeneous earth formations. This method expands the Maxwell's equations in the transverse direction, constructs the relationship between propagator matrix and reflection matrix, and obtains the solution by using the reflection matrix. We systematically derived the formulas of propagator matrix method in isotropic media, uniaxially anisotropic media, fully anisotropic media, and radially inhomogeneous media respectively. In order to obtain the propagator matrix in complex media, we used the fourth-order Runge-Kutta scheme. Numerical experiments show that, compared with traditional methods, the propagator matrix method has wide range of applications while maintaining low computational costs and high accuracy. All algorithms presented in the paper have been parallelized and implemented on a high-performance computing platform. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
10. New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
- Author
-
Li, Shengguo, Liao, Xiangke, Liu, Jie, and Jiang, Hao
- Subjects
- *
EIGENVALUES , *MATRICES (Mathematics) , *CAUCHY problem , *ALGORITHMS , *APPROXIMATION theory - Abstract
In this paper, two accelerated divide-and-conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N2r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy-like matrices and are off-diagonally low-rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low-rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off-diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
11. Revisiting the matrix-free solution of Markov regenerative processes.
- Author
-
Amparore, Elvio Gilberto and Donatelli, Susanna
- Subjects
- *
MARKOV processes , *MATRICES (Mathematics) , *ALGORITHMS , *INVARIANT subspaces , *APPROXIMATION theory , *RANDOM variables , *MATHEMATICAL models - Abstract
SUMMARY In this paper, we revisit the steady-state solution method for Markov Regenerative Processes (MRP) proposed in the work by German. This method solves the embedded Markov chain P of the MRP without storing the matrix P explicitly. We address three issues left open in German's Work: 1) the solution method is restricted to Power method; 2) it has been defined only for ergodic MRPs; and 3) no preconditioning is available to speed-up the computation. This paper discusses how to lift these limitations by extending the algorithm to preconditioned Krylov-subspace methods and by generalizing it to the non-ergodic case. An MRP-specific preconditioner is also proposed, which is built from a sparse approximation of the MRP matrix, computed via simulation. An experimental assessment of the proposed preconditioner is then provided. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
12. Tight and efficient enclosure of matrix multiplication by using optimized BLAS.
- Author
-
Ozaki, Katsuhisa, Ogita, Takeshi, and Oishi, Shin'ichi
- Subjects
- *
MULTIPLICATION , *MATHEMATICAL optimization , *MATRICES (Mathematics) , *ALGORITHMS , *NUMERICAL analysis , *FIXED point theory - Abstract
This paper is concerned with the tight enclosure of matrix multiplication AB for two floating-point matrices A and B. The aim of this paper is to compute component-wise upper and lower bounds of the exact result C of the matrix multiplication AB by floating-point arithmetic. Namely, an interval matrix enclosing C is obtained. In this paper, new algorithms for enclosing C are proposed. The proposed algorithms are designed to mainly exploit the level 3 operations in BLAS. Although the proposed algorithms take around twice as much costs as a standard algorithm promoted by Oishi and Rump, the accuracy of the result by the proposed algorithms is better than that of the standard algorithm. At the end of this paper, we present numerical examples showing the efficiency of the proposed algorithms. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
13. A backward stability analysis of diagonal pivoting methods for solving unsymmetric tridiagonal systems without interchanges.
- Author
-
Erway, Jennifer B. and Marcia, Roummel F.
- Subjects
- *
FACTORIZATION , *MATRICES (Mathematics) , *COLUMNS , *GROWTH factors , *LINEAR systems , *LINEAR algebra , *ALGORITHMS - Abstract
This paper concerns the LBM factorization of unsymmetric tridiagonal matrices, where L and M are unit lower triangular matrices and B is block diagonal with 1×1 and 2×2 blocks. In some applications, it is necessary to form this factorization without row or column interchanges while the tridiagonal matrix is formed. Bunch and Kaufman proposed a pivoting strategy without interchanges specifically for symmetric tridiagonal matrices, and more recently, Bunch and Marcia proposed pivoting strategies that are normwise backward stable for linear systems involving such matrices. In this paper, we extend these strategies to the unsymmetric tridiagonal case and demonstrate that the proposed methods both exhibit bounded growth factors and are normwise backward stable. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
14. Minimal cycle basis of graph products for the force method of frame analysis.
- Author
-
Kaveh, A. and Mirzaie, R.
- Subjects
- *
ALGORITHMS , *EQUILIBRIUM , *GRAPHIC methods , *MATRICES (Mathematics) , *LEXICOGRAPHY - Abstract
For an efficient force method of frame analysis, the formation of localized self-equilibrating systems is an important issue. Such systems can be constructed on minimal cycle basis of the graph model of the structure. In this paper, algorithms are presented for the formation of minimal cycle bases of graph products corresponding to sparse cycle adjacency matrices, leading to the formation of highly sparse flexibility matrices. The algorithms presented employ concepts from three graph products namely Cartesian, strong Cartesian and lexicographic products. Though the formulation for the first two products exist, however, efficient implementations are made in this paper. The formulation for the generation of minimal cycle basis is extended to the lexicographic product. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
15. AN EXCLUSIVE REGRESSORS BINARY MIXTURE MODEL WITH AN APPLICATION TO LABOUR SUPPLY.
- Author
-
Zeng-Hua Lu and Brown, Bruce M.
- Subjects
- *
REGRESSION analysis , *MATHEMATICAL variables , *ALGORITHMS , *MATRICES (Mathematics) , *LABOR supply - Abstract
This paper suggests a new type of mixture regression model, in which each mixture component is explained by its own regressors. Thus, the dependent variable can be driven by one of several unobservable explanatory mechanisms, each of which has its own distinct variables. An extension of the simulated annealing algorithm is introduced to fit this general mixture model. The paper also suggests a new technique for estimating the covariance matrix of estimators in a mixture model. Finally, empirical studies of a labour supply example show that our proposed model can perform much better than conventional logistic or mixture models. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
16. Piecewise travelling-wave basis functions for wires.
- Author
-
Garcí-Tuñón, I., Rodríguez, J. L., Taboada, J. M., and Obelleiro, F.
- Subjects
- *
MOMENTS method (Statistics) , *WIRE , *RADIAL basis functions , *TRAVELING wave antennas , *ALGORITHMS , *MATRICES (Mathematics) - Abstract
This paper presents a method of moments (MoM) formulation for large thin-wire structures. In our approach, a modified version of the well-known Rao–Wilton–Glisson (RWG) basis functions for wires including a linear phase term is considered. This additional term allows an efficient representation of the travelling-wave modes on each wire, while it preserves the main advantages of RWG bases for arbitrarily complex wire topologies. The paper contains a detailed description of the algorithm used for the computation of the impedance matrix integrals. Finally, some results for scattering problems are presented to show the agreement with the conventional RWG-MoM solution. © 2006 Wiley Periodicals, Inc. Microwave Opt Technol Lett 48: 960–966, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.21533 [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
17. The modulus-based matrix splitting algorithms for a class of weakly nonlinear complementarity problems.
- Author
-
Huang, Na and Ma, Changfeng
- Subjects
- *
MATRICES (Mathematics) , *ALGORITHMS , *SET theory , *NONLINEAR theories , *LINEAR complementarity problem , *BOUNDARY value problems , *FIXED point theory , *STOCHASTIC convergence - Abstract
In this paper, we study a class of weakly nonlinear complementarity problems arising from the discretization of free boundary problems. By reformulating the complementarity problems as implicit fixed-point equations based on splitting of the system matrices, we propose a class of modulus-based matrix splitting algorithms. We show their convergence by assuming that the system matrix is positive definite. Moreover, we give several kinds of typical practical choices of the modulus-based matrix splitting iteration methods based on the different splitting of the system matrix. Numerical experiments on two model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of our modulus-based matrix splitting algorithms. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
18. A new two-phase structure-preserving doubling algorithm for critically singular M-matrix algebraic Riccati equations.
- Author
-
Huang, Tsung Ming, Huang, Wei Qiang, Li, Ren Cang, and Lin, Wen Wei
- Subjects
- *
ALGORITHMS , *MATHEMATICAL singularities , *MATRICES (Mathematics) , *ALGEBRAIC equations , *NUMERICAL solutions to Riccati equation , *ITERATIVE methods (Mathematics) - Abstract
Among numerous iterative methods for solving the minimal nonnegative solution of an M-matrix algebraic Riccati equation, the structure-preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank-one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank-one component can be accurately recovered. We then propose an efficient hybrid method, called the two-phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two-phase SDA saves those SDA iterative steps that previously have to have for the rank-one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two-phase SDA. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
19. Realizing an Arbitrary Conductance Matrix via Operational Amplifier and Its Applications.
- Author
-
Imai, Yukio
- Subjects
- *
OPERATIONAL amplifiers , *ELECTRONIC amplifiers , *MATRICES (Mathematics) , *ELECTRIC networks , *ALGORITHMS , *ELECTRONICS - Abstract
This paper presents a realization of an arbitrary conductance matrix using operational amplifiers, together with same applications. It is shown first that any conductance matrix can be realized using operational amplifiers, and the design algorithm which is convenient in the realization is given in the form of a flowchart. Then as an application, a construction of a practical matched bilateral amplifier is presented, together with its application. The realization of a gyrator is also shown. The method presented in this paper is a new and simple way to realize an arbitrary conductance matrix. The matched bilateral amplifier obtained by the proposed method is simple and better than the traditional circuit in terms of the number of circuit elements, element sensitivity, adjustment of the matching impedance, dynamic range and stability. As a practical example of application, the circuit is applied to the four-line carrier telephone link. [ABSTRACT FROM AUTHOR]
- Published
- 1989
- Full Text
- View/download PDF
20. An Approach to the Associative Memorization Using Binary Logic Operations.
- Author
-
Mihara, Masaaki, Kobayashi, Toshifumi, and Yamada, Michihiro
- Subjects
- *
ARTIFICIAL neural networks , *COMPUTERS , *MATRICES (Mathematics) , *MATHEMATICS , *ALGORITHMS - Abstract
The traditional neural system which conducts the paired association has the real coupling coefficients and is not suited to the implementation on digital processing LSI because of its analog property. From such a viewpoint, this paper applies the traditional idea of calculating the coupling coefficients on the real field to the binary field and proposes a system which conducts the paired association using only the logic operation. More precisely, it is noted that the associative law applies to the matrix operation on the real field as well as the matrix operation for the binary code. The coupling coefficients for the binary code for the paired association arc derived by applying the sweeping-out method to the matrix of binary numbers. By this approach, a paired-associate system is obtained by a simpler training algorithm with easy LSI implementation. This paper describes first the traditional solution of the paired-associate problem on the real field and then proposes a method of solution based on that approach for the paired-associate problem on the binary field. The existence condition for the solution of the paired- associate problem is discussed for the proposed method. Finally, the noise-reduction power of the proposed method is estimated. [ABSTRACT FROM AUTHOR]
- Published
- 1992
- Full Text
- View/download PDF
21. Finite-time H ∞ control for discrete-time switched nonlinear systems with time delay.
- Author
-
Zong, Guangdeng, Wang, Ruihua, Zheng, Weixing, and Hou, Linlin
- Subjects
- *
LINEAR matrix inequalities , *ALGORITHMS , *MATHEMATICAL inequalities , *CLOSED loop systems , *MATRICES (Mathematics) - Abstract
In this paper, the problem of finite-time H ∞ control is addressed for a class of discrete-time switched nonlinear systems with time delay. The concept of H ∞ finite-time boundedness is first introduced for discrete-time switched delay systems. Next, a set of switching signals are designed by using the average dwell time approach, under which some delay-dependent sufficient conditions are derived to guarantee the H ∞ finite-time boundedness of the closed-loop system. Then, a finite-time H ∞ state feedback controller is also designed by solving such conditions. Furthermore, the problem of uniform finite-time H ∞ stabilization is also resolved. All the conditions are cast into linear matrix inequalities, which can be easily checked by using recently developed algorithms for solving linear matrix inequalities. A numerical example and a water-quality control system are provided to demonstrate the effectiveness of the main results. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
22. Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis.
- Author
-
Kressner, Daniel and Roman, Jose E.
- Subjects
- *
CHEBYSHEV polynomials , *ALGORITHMS , *MATRICES (Mathematics) , *PROBLEM solving , *EIGENVALUES , *NONLINEAR theories - Abstract
SUMMARY Novel memory-efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so-called quadratic Arnoldi method and two-level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift-and-invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
23. A fast convergent iterative solver for approximate inverse of matrices.
- Author
-
Soleymani, F.
- Subjects
- *
STOCHASTIC convergence , *ITERATIVE methods (Mathematics) , *APPROXIMATION theory , *MATRIX inversion , *ALGORITHMS , *MATRICES (Mathematics) - Abstract
SUMMARY In this paper, a rapid iterative algorithm is proposed to find robust approximations for the inverse of nonsingular matrices. The analysis of convergence reveals that this high-order method possesses eighth-order convergence. The interesting point is that, this rate is attained using less number of matrix-by-matrix multiplications in contrast to the existing methods of the same type in the literature. The extension of the method for finding Moore-Penrose inverse of singular or rectangular matrices is also presented. Numerical comparisons will be given to show the applicability, stability and consistency of the new scheme by paying special attention on the computational time. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
24. An algorithm for constructing a pseudo-Jacobi matrix from given spectral data.
- Author
-
Bebiano, N., Furtado, S., and Providência, J.
- Subjects
- *
ALGORITHMS , *JACOBI method , *MATRICES (Mathematics) , *SPECTRAL theory , *QUANTUM theory , *TOPOLOGICAL spaces , *INDEFINITE inner product spaces - Abstract
SUMMARY The main purpose of this paper is the extension of the classical spectral direct and inverse analysis of Jacobi matrices for the non-self-adjoint setting. Matrices of this class appear in the context of non-Hermitian quantum mechanics. The reconstruction of a pseudo-Jacobi matrix from its spectrum and the spectra of two complementary principal matrices is investigated in the context of indefinite inner product spaces. An existence and uniqueness theorem is given, and a strikingly simple algorithm, based on the Euclidean division algorithm, to reconstruct the matrix from the spectral data is presented. A result of Friedland and Melkman stating a necessary and sufficient condition for a real sequence to be the spectrum of a non-negative Jacobi matrix is revisited and generalized. Namely, it is shown that a suitable set of prescribed eigenvalues defines a unique non-negative pseudo-Jacobi matrix, which is J-Hermitian for a fixed J. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
25. GB-to-TNT: facilitating creation of matrices from GenBank and diagnosis of results in TNT.
- Author
-
Goloboff, Pablo A. and Catalano, Santiago A.
- Subjects
- *
MATRICES (Mathematics) , *TAXONOMY , *GENOMES , *PHYLOGENY , *ALGORITHMS - Abstract
This paper presents a pipeline, implemented in an open-source program called GB→TNT (GenBank-to-TNT), for creating large molecular matrices, starting from GenBank files and finishing with TNT matrices which incorporate taxonomic information in the terminal names. GB→TNT is designed to retrieve a defined genomic region from a bulk of sequences included in a GenBank file. The user defines the genomic region to be retrieved and several filters (genome, length of the sequence, taxonomic group, etc.); each genomic region represents a different data block in the final TNT matrix. GB→TNT first generates Fasta files from the input GenBank files, then creates an alignment for each of those (by calling an alignment program), and finally merges all the aligned files into a single TNT matrix. The new version of TNT can make use of the taxonomic information contained in the terminal names, allowing easy diagnosis of results, evaluation of fit between the trees and the taxonomy, and automatic labelling or colouring of tree branches with the taxonomic groups they represent. © The Willi Hennig Society 2012. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
26. Iterative Sinc− convolution method for solving planar D-bar equation with application to EIT Iterative Sinc− convolution method for solving planar D-bar equation with application to EIT.
- Author
-
Abbasi, Mahdi and Naghsh-Nilchi, Ahmad-Reza
- Subjects
- *
INTEGRAL equations , *MATHEMATICAL convolutions , *NUMERICAL analysis , *INVERSE scattering transform , *ALGORITHMS , *EQUATIONS , *MATRICES (Mathematics) - Abstract
SUMMARY The numerical solution of D-bar integral equations is the key in inverse scattering solution of many complex problems in science and engineering including conductivity imaging. Recently, a couple of methodologies were considered for the numerical solution of D-bar integral equation, namely product integrals and multigrid. The first one involves high computational complexity and other one has low convergence rate disadvantages. In this paper, a new and efficient sinc-convolution algorithm is introduced to solve the two-dimensional D-bar integral equation to overcome both of these disadvantages and to resolve the singularity problem not tackled before effectively. The method of sinc-convolution is based on using collocation to replace multidimensional convolution-form integrals- including the two-dimensional D-bar integral equations - by a system of algebraic equations. Separation of variables in the proposed method allows elimination of the formulation of the huge full matrices and therefore reduces the computational complexity drastically. In addition, the sinc-convolution method converges exponentially with a convergence rate of [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
27. SDF classifier revisited.
- Author
-
Smiatacz, Maciej and Malina, Witold
- Subjects
- *
MATRIX analytic methods , *DATA structures , *ELECTRONIC data processing , *DATABASE design , *DATABASE management , *ALGORITHMS , *MATRICES (Mathematics) - Abstract
This paper is addressing problems related to the construction of classifiers based on the Similarity Discriminant Function (SDF), in which the traditional vector representation of a pattern is replaced with matrix data. We introduce potential modifications of the matrix data structure and propose new variants of the SDF. The algorithms that we present were tested on images of handwritten digits and on photographs of human faces, taken from the ORL and CMU-PIE databases. The results of experiments show that our modifications significantly improved the performance of the original SDF classifier. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
28. A New Loosely Coupled DCM Based GPS/INS Integration Method.
- Author
-
Edwan, Ezzaldeen, Zhou, Junchuan, Zhang, Jieying, and Loffeld, Otmar
- Subjects
- *
GLOBAL Positioning System , *MATRICES (Mathematics) , *ALGORITHMS , *PERFORMANCE evaluation , *MOTIVATION (Psychology) , *SIMULATION methods & models , *KALMAN filtering - Abstract
ABSTRACT In this paper, we derive a GPS/INS integration algorithm based on the direction cosine matrix (DCM) attitude representation model and analyze its performance. The motivation for this work is to find an algorithm that is capable of tracking the variation of the gyro bias vector during operations and that benefits from the established DCM based attitude estimation algorithms. Filter performance is evaluated using a simulation based on an air vehicle trajectory profile and is compared with an Euler angles-based unscented Kalman filter (UKF). We investigate the effects of improper initialization of the state vector on the filter performance. These results are supplemented using experimental data collected along a car route with two different grades of inertial measurement units (IMUs). The DCM based model has some advantages over other attitude representations due to its relatively moderate computational load and applicability with different categories of inertial sensors. Copyright © 2012 Institute of Navigation [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
29. An alternating direction method for linear-constrained matrix nuclear norm minimization.
- Author
-
Xiao, Yun-Hai and Jin, Zheng-Fen
- Subjects
- *
LINEAR systems , *MATRICES (Mathematics) , *PROBLEM solving , *ITERATIVE methods (Mathematics) , *CONTROL theory (Engineering) , *MATHEMATICAL models , *LAGRANGIAN functions , *ALGORITHMS - Abstract
SUMMARY The aim of the nuclear norm minimization problem is to find a matrix that minimizes the sum of its singular values and satisfies some constraints simultaneously. Such a problem has received more attention largely because it is closely related to the affine rank minimization problem, which appears in many control applications including controller design, realization theory, and model reduction. In this paper, we first propose an exact version alternating direction method for solving the nuclear norm minimization problem with linear equality constraints. At each iteration, the method involves a singular value thresholding and linear matrix equations which are solved exactly. Convergence of the proposed algorithm is followed directly. To broaden the capacity of solving larger problems, we solve approximately the subproblem by an iterative method with the Barzilai-Borwein steplength. Some extensions to the noisy problems and nuclear norm regularized least-square problems are also discussed. Numerical experiments and comparisons with the state-of-the-art method FPCA show that the proposed method is effective and promising. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
30. Data fusion-based interference matrix generation for cellular system frequency planning.
- Author
-
Wu, Zhouyun, Huang, Aiping, Zhou, Haojie, Hua, Cunqing, and Qian, Jun
- Subjects
- *
MATRICES (Mathematics) , *MULTISENSOR data fusion , *CELL phone systems , *MEASUREMENT , *ALGORITHMS , *DATA transmission systems - Abstract
Interference matrix (IM) has been widely used in frequency planning/optimization of cellular systems because it describes the interaction between any two cells. IM is generated from the source data gathered from the cellular system, either mobile measurement reports (MMRs) or drive test (DT) records. IM accuracy is not satisfactory since neither MMRs nor DT records contain complete information on interference and traffic distribution. In this paper, two IM generation algorithms based on source data fusion are proposed. Data fusion in one algorithm is to reinforce MMRs data, using the frequency-domain information of DT data from the same region. Data fusion in the other algorithm is to reshape DT data, using the traffic distribution information extracted from MMRs from the same region. The fused data contain more complete information so that more accurate IM can be obtained. Simulation results have validated this conclusion. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
31. An algorithm for direct identification of passive transfer matrices with positive real fractions via convex programming.
- Author
-
De Tommasi, L., de Magistris, M., Deschrijver, D., and Dhaene, T.
- Subjects
- *
ALGORITHMS , *MATRICES (Mathematics) , *FRACTIONS , *CONVEX programming , *SYSTEMS theory , *QUADRATIC programming , *CONSTRAINT satisfaction - Abstract
The paper presents a new algorithm for the identification of a positive real rational transfer matrix of a multi-input-multi-output system from frequency domain data samples. It is based on the combination of least-squares pole identification by the Vector Fitting algorithm and residue identification based on frequency-independent passivity constraints by convex programming. Such an approach enables the identification of a priori guaranteed passive lumped models, so avoids the passivity check and subsequent (perturbative) passivity enforcement as required by most of the other available algorithms. As a case study, the algorithm is successfully applied to the macro-modeling of a twisted cable pair, and the results compared with a passive identification performed with an algorithm based on quadratic programming (QPpassive), highlighting the advantages of the proposed formulation. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
32. Short note: An integrable numerical algorithm for computing eigenvalues of a specially structured matrix.
- Author
-
Sun, Jian-Qing, Hu, Xing-Biao, and Tam, Hon-Wah
- Subjects
- *
NUMERICAL analysis , *ALGORITHMS , *EIGENVALUES , *LATTICE theory , *ASYMPTOTIC expansions , *MATRICES (Mathematics) - Abstract
This paper is motivated by some recent work of Fukuda, Ishiwata, Iwasaki, and Nakamura ( Inverse Problems 2009; :015007). We first design an algorithm for computing the eigenvalues of a specially structured matrix from the discrete Bogoyavlensky Lattice 2 (dBL2) system. A Lax representation for the dBL2 system is given in a matrix form. By considering the asymptotic behavior of dBL2 variables, some characteristic polynomials are then factorized. A new algorithm for computing the complex eigenvalues of a specially structured matrix is then introduced. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
33. A revision of extended division algorithm for polynomial matrices and its applications.
- Author
-
Kase, Wataru
- Subjects
- *
ALGORITHMS , *TRANSFER functions , *DIFFERENTIAL equations , *MODIFICATIONS , *POLYNOMIALS , *MATRICES (Mathematics) , *EDUCATION - Abstract
In this paper, the extended division algorithm for polynomial matrices proposed in Ref. 2 will be revised. The revised version of the algorithm divides the polynomial matrix part and the strictly proper transfer function matrix part for a given improper transfer function matrix, which is useful for analysis and synthesis. Using the new version, a calculation of stabilizing controllers corresponding to the design in state space will be discussed. © 2010 Wiley Periodicals, Inc. Electron Comm Jpn, 93(5): 1–7, 2010; Published online in Wiley InterScience (
www.interscience.wiley.com ). DOI 10.1002/ecj.10298 [ABSTRACT FROM AUTHOR]- Published
- 2010
- Full Text
- View/download PDF
34. Selecting good views of high-dimensional data using class consistency.
- Author
-
Sips, Mike, Neubert, Boris, Lewis, John P., and Hanrahan, Pat
- Subjects
- *
DATA visualization , *DATA analysis , *VISUALIZATION , *ALGORITHMS , *ORTHOGONAL functions , *MATRICES (Mathematics) - Abstract
Many visualization techniques involve mapping high-dimensional data spaces to lower-dimensional views. Unfortunately, mapping a high-dimensional data space into a scatterplot involves a loss of information; or, even worse, it can give a misleading picture of valuable structure in higher dimensions. In this paper, we propose class consistency as a measure of the quality of the mapping. Class consistency enforces the constraint that classes of n–D data are shown clearly in 2–D scatterplots. We propose two quantitative measures of class consistency, one based on the distance to the class's center of gravity, and another based on the entropies of the spatial distributions of classes. We performed an experiment where users choose good views, and show that class consistency has good precision and recall. We also evaluate both consistency measures over a range of data sets and show that these measures are efficient and robust. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
35. A smoothing Newton's method for the construction of a damped vibrating system from noisy test eigendata.
- Author
-
Bai, Zheng-Jian and Ching, Wai-Ki
- Subjects
- *
VIBRATION (Mechanics) , *MASS (Physics) , *DAMPING (Mechanics) , *MATRICES (Mathematics) , *ALGORITHMS - Abstract
In this paper we consider an inverse problem for a damped vibration system from the noisy measured eigendata, where the mass, damping, and stiffness matrices are all symmetric positive-definite matrices with the mass matrix being diagonal and the damping and stiffness matrices being tridiagonal. To take into consideration the noise in the data, the problem is formulated as a convex optimization problem involving quadratic constraints on the unknown mass, damping, and stiffness parameters. Then we propose a smoothing Newton-type algorithm for the optimization problem, which improves a pre-existing estimate of a solution to the inverse problem. We show that the proposed method converges both globally and quadratically. Numerical examples are also given to demonstrate the efficiency of our method. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
36. Analysis of frames by substructuring technique based on using algebraic and graph methods.
- Author
-
Kaveh, A. and Fazli, H.
- Subjects
- *
ALGORITHMS , *MATRICES (Mathematics) , *UNIVERSAL algebra , *UNIVERSAL enveloping algebras , *BOUNDARY value problems - Abstract
In this paper, substructuring techniques for the analysis of frame structures by the force method are reviewed. An algorithm is presented for the formation of cycle basis of the graph model of a frame structure. A simple and efficient graph method is proposed for preserving the sparsity of the matrices involved for including the boundary conditions when algebraic and graph force methods are employed. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
37. Solutions of symmetry-constrained least-squares problems.
- Author
-
Zhen-Yun Peng
- Subjects
- *
ITERATIVE methods (Mathematics) , *LEAST squares , *ALGORITHMS , *MATHEMATICAL analysis , *LINEAR algebra , *MATRICES (Mathematics) - Abstract
In this paper, two new matrix-form iterative methods are presented to solve the least-squares problem:
\documentclass{article}\usepackage[mathscr]{euscript}\usepackage{amssymb,amsbsy,rotating}\footskip=0pc\pagestyle{empty}\begin{document}\[ \min\limits_{X\in {\mathscr{S}}_1,Y\in {\mathscr{S}}_2}\|AXB+CYD-E\| \]\end{document} and matrix nearness problem:\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\[ \min\limits_{[X: Y]\in S_{XY}}\|[X: Y]-[\widetilde{X}:\widetilde{Y}]\| \] \end{document} where matrices$A\in R^{p\times n_1},B\in R^{n_2\times q},C\in R^{p\times m_1},D\in R^{m_2\times q},E\in R^{p\times q},\widetilde{X}\in R^{n_1\times n_2}$ and$\widetilde{Y}\in R^{m_1\times m_2}$ are given; 𝒮1 and 𝒮2 are the set of constraint matrices, such as symmetric, skew symmetric, bisymmetric and centrosymmetric matrices sets and SXY is the solution pair set of the minimum residual problem. These new matrix-form iterative methods have also faster convergence rate and higher accuracy than the matrix-form iterative methods proposed by Peng and Peng (Numer. Linear Algebra Appl. 2006; 13: 473–485) for solving the linear matrix equation AXB+CYD=E. Paige's algorithms, which are based on the bidiagonalization procedure of Golub and Kahan, are used as the framework for deriving these new matrix-form iterative methods. Some numerical examples illustrate the efficiency of the new matrix-form iterative methods. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]- Published
- 2008
- Full Text
- View/download PDF
38. Design of precompensator for a diagonal interactor using Markov parameters.
- Author
-
Mutoh, Yasuhiko
- Subjects
- *
CONTROL theory (Engineering) , *MARKOV processes , *NONLINEAR control theory , *ALGORITHMS , *MATRICES (Mathematics) - Abstract
An interactor plays a basic role in the design problems of multivariable control systems, such as the model matching control, decoupling control, adaptive control, and disturbance decoupling control. For example, it is well known that a linear multivariable system is decouplable by the static state feedback if and only if it has a diagonal interactor. But, in general, the interactor is a lower left triangular matrix, which makes the design problems of multivariable control systems complicated. From this point of view, the precompensator such that the total system has a diagonal interactor is important for multivariable control systems to simplify their design procedure. This paper concerns the systematic design method of the precompensator for a diagonal interactor using Markov parameters of the plant. It will also be proved that this compensator is always obtained by the proposed design algorithm. Furthermore, this argument will be a basic idea when this technique is applied to the nonlinear multivariable systems. © 2008 Wiley Periodicals, Inc. Electr Eng Jpn, 163(1): 65–72, 2008; Published online in Wiley InterScience (
www.interscience.wiley.com ). DOI 10.1002/eej.20599 [ABSTRACT FROM AUTHOR]- Published
- 2008
- Full Text
- View/download PDF
39. Matrix converter control using direct AC/AC conversion approach to reduce output voltage harmonics.
- Author
-
Takeshita, Takaharu and Shimada, Hiroshi
- Subjects
- *
CASCADE converters , *MATRICES (Mathematics) , *ELECTRIC potential , *ELECTRICAL harmonics , *COMMUTATION (Electricity) , *ALGORITHMS - Abstract
This paper presents a control scheme for matrix converters for reducing the output voltage harmonics. The proposed control scheme is based on the direct AC/AC conversion approach and the carrier-based PWM control to obtain the constant switching frequency. The proposed scheme can achieve simultaneous control of both the output voltage and the input power factor. A feature of the proposed control scheme is the reduction of both the output voltage harmonics and the number of instances of commutations. The effectiveness of the proposed control algorithm for a matrix converter has been verified by simulations. © 2007 Wiley Periodicals, Inc. Electr Eng Jpn, 162(2): 61–72, 2008; Published online in Wiley InterScience (
www.interscience.wiley.com ). DOI 10.1002/eej.20550 [ABSTRACT FROM AUTHOR]- Published
- 2008
- Full Text
- View/download PDF
40. Fast algorithms for designing variable FIR notch filters.
- Author
-
Routray, Aurobinda and Swain, Smarak
- Subjects
- *
ALGORITHMS , *AUTOCORRELATION (Statistics) , *TOEPLITZ matrices , *MATHEMATICAL optimization , *MATRICES (Mathematics) - Abstract
The paper presents fast algorithms for designing finite impulse response (FIR) notch filters. The aim is to design a digital FIR notch filter so that the magnitude of the filter has a deep notch at a specified frequency, and as the notch frequency changes, the filter coefficients should be able to track the notch fast in real time. The filter design problem is first converted into a convex optimization problem in the autocorrelation domain. The frequency response of the autocorrelation of the filter impulse response is compared with the desired filter response and the integral square error is minimized with respect to the unknown autocorrelation coefficients. Spectral factorization is used to calculate the coefficients of the filter. In the optimization process, the computational advantage is obtained by exploiting the structure of the Hessian matrix which consists of a Toeplitz plus a Hankel matrix. Two methods have been used for solving the Toeplitz-plus-Hankel system of equations. In the first method, the computational time is reduced by using Block–Levinson's recursion for solving the Toeplitz-plus-Hankel system of matrices. In the second method, the conjugate gradient method with different preconditioners is used to solve the system. Comparative studies demonstrate the computational advantages of the latter. Both these algorithms have been used to obtain the autocorrelation coefficients of notch filters with different orders. The original filter coefficients are found by spectral factorization and each of these filters have been tested for filtering synthetic as well as real-life signals. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
41. A new method for mining of WWW access sequences.
- Author
-
Oyanagi, Shigeru, Kamiharako, Masatoshi, Kubota, Kazuto, and Nakase, Akihiko
- Subjects
- *
WORLD Wide Web , *WEBSITES , *MATRICES (Mathematics) , *ALGORITHMS , *MATHEMATICAL sequences - Abstract
Analysis of access sequences is an important technique in the mining of WWW access logs. The well-known apriori algorithm is a typical method. A problem of this method is that the obtained relation between sequences is not reflected in the output. This paper proposes a new method of sequence analysis using matrix clustering. This method considers a binary matrix in which the sequences correspond to the rows and ordered pairs of pages correspond to the columns. The similarities between sequences are extracted as clusters in the matrix. Based on these clusters, super-sequences, which are generalizations of similar sequences, can be generated. The proposed method is applied to real data and the results are evaluated. It is verified that the features of entire sequences can be extracted. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 90(10): 127–138, 2007; Published online in Wiley InterScience (
www.interscience.wiley.com ). DOI 10.1002/ecjb.20394 [ABSTRACT FROM AUTHOR]- Published
- 2007
- Full Text
- View/download PDF
42. Kronecker product approximations for dense block Toeplitz-plus-Hankel matrices.
- Author
-
Kilmer, M. E. and Nagy, J. G.
- Subjects
- *
KRONECKER products , *MATRICES (Mathematics) , *FACTORIZATION , *IMAGE processing , *ALGORITHMS - Abstract
In this paper, we consider the approximation of dense block Toeplitz-plus-Hankel matrices by sums of Kronecker products of Toeplitz-plus-Hankel matrices. We present an algorithm for efficiently computing the matrix approximation that requires the factorization of matrices of much smaller dimension than that of the original. The main results are described for block Toeplitz matrices with Toeplitz-plus-Hankel blocks, but the algorithms can be readily adjusted for other related structures that arise in image processing applications, such as block Toeplitz with Toeplitz blocks and block Toeplitz-plus-Hankel with Toeplitz-plus-Hankel blocks. Our work extends the techniques in Kamm and Nagy (SIAM J. Matrix Anal. Appl. 2000; 22:155–172) and Nagy et al. (SIAM J. Matrix Anal. Appl. 2004; 25:829–841), which consider similar matrices, but with the added restriction that the matrices have a banded/block-banded structure. We illustrate the effectiveness of our algorithm by using the output of the algorithm to construct preconditioners for systems from two different applications: diffuse optical tomography and atmospheric image deblurring. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
43. A Rayleigh quotient minimization algorithm based on algebraic multigrid.
- Author
-
Hetmaniuk, U.
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATRICES (Mathematics) , *RAYLEIGH quotient , *GEOMETRY - Abstract
This paper presents a new algebraic extension of the Rayleigh quotient multigrid (RQMG) minimization algorithm to compute the smallest eigenpairs of a symmetric positive definite pencil (A, M). Earlier versions of RQMG minimize the Rayleigh quotient over a hierarchy of geometric grids. We replace the geometric mesh information with the algebraic information defined by an algebraic multigrid preconditioner. At each level, we minimize the Rayleigh quotient with a block preconditioned algorithm. Numerical experiments illustrate the efficiency of this new algorithm to compute several eigenpairs. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
44. Analysis of block matrix preconditioners for elliptic optimal control problems.
- Author
-
Mathew, T. P., Sarkis, M., and Schaerer, C. E.
- Subjects
- *
MATRICES (Mathematics) , *ALGORITHMS , *OPERATIONS research , *LINEAR differential equations , *BOUNDARY value problems , *METHODOLOGY - Abstract
In this paper, we describe and analyse several block matrix iterative algorithms for solving a saddle point linear system arising from the discretization of a linear-quadratic elliptic control problem with Neumann boundary conditions. To ensure that the problem is well posed, a regularization term with a parameter α is included. The first algorithm reduces the saddle point system to a symmetric positive definite Schur complement system for the control variable and employs conjugate gradient (CG) acceleration, however, double iteration is required (except in special cases). A preconditioner yielding a rate of convergence independent of the mesh size h is described for Ω ⊂ R2 or R3, and a preconditioner independent of h and α when Ω ⊂ R2. Next, two algorithms avoiding double iteration are described using an augmented Lagrangian formulation. One of these algorithms solves the augmented saddle point system employing MINRES acceleration, while the other solves a symmetric positive definite reformulation of the augmented saddle point system employing CG acceleration. For both algorithms, a symmetric positive definite preconditioner is described yielding a rate of convergence independent of h. In addition to the above algorithms, two heuristic algorithms are described, one a projected CG algorithm, and the other an indefinite block matrix preconditioner employing GMRES acceleration. Rigorous convergence results, however, are not known for the heuristic algorithms. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
45. Direct algorithms to solve the two-sided obstacle problem for an M-matrix.
- Author
-
Zeng, J. P. and Jiang, Y. J.
- Subjects
- *
ALGORITHMS , *MATRICES (Mathematics) , *COMPUTATIONAL complexity , *POLYNOMIALS , *ALGEBRA , *MATHEMATICS - Abstract
In this paper, two direct algorithms for solving the two-sided obstacle problem with an M-matrix are presented. The algorithms are well defined and have polynomial computational complexity. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
46. Block-row Hankel weighted low rank approximation.
- Author
-
Schuermans, M., Lemmerling, P., and Van Huffel, S.
- Subjects
- *
APPROXIMATION theory , *HANKEL functions , *MATRICES (Mathematics) , *MATHEMATICAL optimization , *ALGORITHMS - Abstract
This paper extends the weighted low rank approximation (WLRA) approach to linearly structured matrices. In the case of Hankel matrices with a special block structure, an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
47. Kronecker product approximations for image restoration with anti-reflective boundary conditions.
- Author
-
Perrone, Lisa
- Subjects
- *
IMAGE reconstruction , *MATRICES (Mathematics) , *KRONECKER products , *ALGORITHMS , *BOUNDARY value problems , *SYMMETRIC matrices , *ABSTRACT algebra - Abstract
The anti-reflective boundary condition for image restoration was recently introduced as a mathematically desirable alternative to other boundary conditions presently represented in the literature. It has been shown that, given a centrally symmetric point spread function (PSF), this boundary condition gives rise to a structured blurring matrix, a submatrix of which can be diagonalized by the discrete sine transform (DST), leading to an O(n2 log n) solution algorithm for an image of size n × n. In this paper, we obtain a Kronecker product approximation of the general structured blurring matrix that arises under this boundary condition, regardless of symmetry properties of the PSF. We then demonstrate the usefulness and efficiency of our approximation in an SVD-based restoration algorithm, the computational cost of which would otherwise be prohibitive. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
48. Ordering techniques for singly bordered block diagonal forms for unsymmetric parallel sparse direct solvers.
- Author
-
Yifan Hu and Scott, Jennifer
- Subjects
- *
LINEAR systems , *SPARSE matrices , *MATRICES (Mathematics) , *EQUATIONS , *ALGORITHMS , *FACTORIZATION , *MATHEMATICS , *VERTEX detectors - Abstract
The solution of large sparse linear systems of equations is one of the cornerstones of scientific computation. In many applications it is important to be able to solve these systems as rapidly as possible. One approach for very large problems is to reorder the system matrix to bordered block diagonal form and then to solve the block system using a coarse-grained parallel approach. In this paper, we consider the problem of efficiently ordering unsymmetric systems to singly bordered block diagonal form. Algorithms such as the MONET algorithm of Hu et al. (Comput. Chem. Eng. 23 (2000) 1631) that depend upon computing a representation of AAT can be prohibitively expensive when a single (or small number of) matrix factorizations are required. We therefore work with the graph of AT + A (or BT + B, where B is a row permutation of A) and propose new reordering algorithms that use only vertex separators and wide separators of this graph. Numerical experiments demonstrate that our methods are efficient and can produce bordered forms that are competitive with those obtained using MONET. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
49. A pivoting strategy for symmetric tridiagonal matrices.
- Author
-
Bunch, James R. and Marcia, Roummel F.
- Subjects
- *
FACTORIZATION , *LINEAR systems , *MATRICES (Mathematics) , *MAGNITUDE estimation , *ALGORITHMS , *COPYRIGHT - Abstract
The LBLT factorization of Bunch for solving linear systems involving a symmetric indefinite tridiagonal matrix T is a stable, efficient method. It computes a unit lower triangular matrix L and a block 1 × 1 and 2 × 2 matrix B such that T=LBLT. Choosing the pivot size requires knowing a priori the largest element σ of T in magnitude. In some applications, it is required to factor T as it is formed without necessarily knowing σ. In this paper, we present a modification of the Bunch algorithm that can satisfy this requirement. We demonstrate that this modification exhibits the same bound on the growth factor as the Bunch algorithm and is likewise normwise backward stable. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
50. Low-complexity minimization algorithms.
- Author
-
Di Fiore, Carmine, Fanelli, Stefano, and Zellini, Paolo
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATRICES (Mathematics) , *ABSTRACT algebra , *UNIVERSAL algebra , *MATHEMATICS - Abstract
Structured matrix algebras ℒ and a generalized BFGS-type iterative scheme have been recently investigated to introduce low-complexity quasi-Newton methods, named ℒQN, for solving general (non-structured) minimization problems. In this paper we introduce the ℒkQN methods, which exploit ad hoc algebras at each step. Since the structure of the updated matrices can be modified at each iteration, the new methods can better fit the Hessian matrix, thereby improving the rate of convergence of the algorithm. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.