The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 20...The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 2006) is used. This transform is fast, has a unique algorithm for any length of the input vector/signal and can be used with different complex basic 2 × 2 transforms. The DsiHT is zeroing all components of the input signal while moving or heaping the energy of the signal to one component, for instance the first one. We describe three different types of QR-decompositions that use the basic transforms with the T, G, and M-type complex matrices we introduce, as well as without matrices but using analytical formulas. We also present the mixed QR-decomposition, when different type DsiHTs are used in different stages of the algorithm. The number of such decompositions is greater than 3<sup>(N-1)</sup>, for an N × N complex matrix. Examples of the QR-decomposition are described in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the known method of Householder transforms. The precision of the QR-decompositions of N × N matrices, when N are 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400 is also compared. The MATLAB-based scripts of the codes for QR-decompositions by the described DsiHTs are given.展开更多
Housecholder变换用于上三角化是基于线性预测误差方程的数据阵。可以证明,由上三角阵的主对角元素便可得到各阶AR模型的残差平方和。因此用逐列处理的方法可以构成 AR 模型化与谱估计的递推算法。在大多数情况下,本文的算法不仅给出与...Housecholder变换用于上三角化是基于线性预测误差方程的数据阵。可以证明,由上三角阵的主对角元素便可得到各阶AR模型的残差平方和。因此用逐列处理的方法可以构成 AR 模型化与谱估计的递推算法。在大多数情况下,本文的算法不仅给出与协方差算法或修正协方差算法相同的计算结果;而且当计算中存在严重的数值病态问题时,协方差法和修正协方差法无法获得好的AR谱估计,而本文的算法则仍然可以获得好的估计。文中给出了典型的计算例子。展开更多
A fast Cholesky decomposition and a fast inverse Cholesky decomposition method for A T A are presented,where A is an m×n rectangular Toeplitz block matrix,we give the FCD algorithm for computing...A fast Cholesky decomposition and a fast inverse Cholesky decomposition method for A T A are presented,where A is an m×n rectangular Toeplitz block matrix,we give the FCD algorithm for computing R , and the FICD algorithm for computing R -1 ,both allow for an efficient parallel implementation,for solving a least squares problem and require only O(mn) operations.展开更多
The standard implementation of the hybrid GMRES algorithm for solving large nonsymmetric linear systems involves a Gram-Schmidt process which is a potential source of significant numerical error. An alternative implem...The standard implementation of the hybrid GMRES algorithm for solving large nonsymmetric linear systems involves a Gram-Schmidt process which is a potential source of significant numerical error. An alternative implementation is outlined here in which orthogonalization by Householder transformations replaces the Gram-Schmidt process. Numerical experiments show that the new implementation is more stable.展开更多
This paper describes a new method of QR-decomposition of square nonsingular matrices (real or complex) by the Givens rotations through the unitary discrete heap transforms. This transforms can be defined by a differen...This paper describes a new method of QR-decomposition of square nonsingular matrices (real or complex) by the Givens rotations through the unitary discrete heap transforms. This transforms can be defined by a different path, or the order of processing components of input data, which leads to different realizations of the QR-decomposition. The heap transforms are fast, because of a simple form of decomposition of their matrices. The direct calculation of the N-point discrete heap transform requires no more than 5(N-1) multiplications, 2(N-1) additions, plus 3(N-1) trigonometric operations. The QR-decomposition of the square matrix N × N uses about 4/3N3 multiplications and N(N-1)/2 square roots. This number varies depending on the path of the heap transform, and it is shown that “the optimal path” allows for significant reduction of number of operations in QR-decomposition. The heap transform and its matrix can be described analytically, and therefore, this transform can also be applied to the QR-decomposition of complex matrices.展开更多
The classical iterative methods for finding roots of nonlinear equations,like the Newton method,Halley method,and Chebyshev method,have been modified previously to achieve optimal convergence order.However,the Househo...The classical iterative methods for finding roots of nonlinear equations,like the Newton method,Halley method,and Chebyshev method,have been modified previously to achieve optimal convergence order.However,the Householder method has so far not been modified to become optimal.In this study,we shall develop two new optimal Newton-Householder methods without memory.The key idea in the development of the new methods is the avoidance of the need to evaluate the second derivative.The methods fulfill the Kung-Traub conjecture by achieving optimal convergence order four with three functional evaluations and order eight with four functional evaluations.The efficiency indices of the methods show that methods perform better than the classical Householder’s method.With the aid of convergence analysis and numerical analysis,the efficiency of the schemes formulated in this paper has been demonstrated.The dynamical analysis exhibits the stability of the schemes in solving nonlinear equations.Some comparisons with other optimal methods have been conducted to verify the effectiveness,convergence speed,and capability of the suggested methods.展开更多
In this papert we give a method to construct multivqriate wavelets for skewsymmetric scaling function. Such wavelets have some desirable properties, e,g.t they are real-valued and orthogonal if the scaling function is...In this papert we give a method to construct multivqriate wavelets for skewsymmetric scaling function. Such wavelets have some desirable properties, e,g.t they are real-valued and orthogonal if the scaling function is real-valued and orthonormalrespectively.展开更多
A fast algorithm FBTQ is presented which computes the QR factorization a block-Toeplitz matrix A (A∈R) in O(mns3) multiplications. We prove that the QR decomposition of A and the inverse Cholesky decomposition can be...A fast algorithm FBTQ is presented which computes the QR factorization a block-Toeplitz matrix A (A∈R) in O(mns3) multiplications. We prove that the QR decomposition of A and the inverse Cholesky decomposition can be computed in parallel using the sametransformation.We also prove that some kind of Toeplltz-block matrices can he transformed into the corresponding block-Toeplitz matrices.展开更多
A fast Cholesky factorization algorithm based on the classical Schur algorithm for themp×mp symmetric positive definite (s. p. d) block-Toeplitz matrices is presented. The relation between the generator and the S...A fast Cholesky factorization algorithm based on the classical Schur algorithm for themp×mp symmetric positive definite (s. p. d) block-Toeplitz matrices is presented. The relation between the generator and the Schur complement of the matrices is explored. Besides, by applying the hyperbolic Householder transformations, we can reach an improved algorithm whose computational complexity is2p 2m3?4pm3+3/2m3+O(pm).展开更多
Householder transform is used to triangularize the data matrix, which is basedon the near prediction error equation. It is proved that the sum of squared residuals for eachAR order can be obtained by the main diagonal...Householder transform is used to triangularize the data matrix, which is basedon the near prediction error equation. It is proved that the sum of squared residuals for eachAR order can be obtained by the main diagonal elements of upper triangular matrix, so thecolumn by column procedure can be used to develop a recursive algorithm for AR modeling andspectral estimation. In most cases, the present algorithm yields the same results as the covariancemethod or modified covariance method does. But in some special cases where the numerical ill-conditioned problems are so serious that the covariance method and modified covariance methodfail to estimate AR spectrum, the presented algorithm still tends to keep good performance. Thetypical computational results are presented finally.展开更多
文摘The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 2006) is used. This transform is fast, has a unique algorithm for any length of the input vector/signal and can be used with different complex basic 2 × 2 transforms. The DsiHT is zeroing all components of the input signal while moving or heaping the energy of the signal to one component, for instance the first one. We describe three different types of QR-decompositions that use the basic transforms with the T, G, and M-type complex matrices we introduce, as well as without matrices but using analytical formulas. We also present the mixed QR-decomposition, when different type DsiHTs are used in different stages of the algorithm. The number of such decompositions is greater than 3<sup>(N-1)</sup>, for an N × N complex matrix. Examples of the QR-decomposition are described in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the known method of Householder transforms. The precision of the QR-decompositions of N × N matrices, when N are 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400 is also compared. The MATLAB-based scripts of the codes for QR-decompositions by the described DsiHTs are given.
文摘Housecholder变换用于上三角化是基于线性预测误差方程的数据阵。可以证明,由上三角阵的主对角元素便可得到各阶AR模型的残差平方和。因此用逐列处理的方法可以构成 AR 模型化与谱估计的递推算法。在大多数情况下,本文的算法不仅给出与协方差算法或修正协方差算法相同的计算结果;而且当计算中存在严重的数值病态问题时,协方差法和修正协方差法无法获得好的AR谱估计,而本文的算法则仍然可以获得好的估计。文中给出了典型的计算例子。
文摘A fast Cholesky decomposition and a fast inverse Cholesky decomposition method for A T A are presented,where A is an m×n rectangular Toeplitz block matrix,we give the FCD algorithm for computing R , and the FICD algorithm for computing R -1 ,both allow for an efficient parallel implementation,for solving a least squares problem and require only O(mn) operations.
文摘The standard implementation of the hybrid GMRES algorithm for solving large nonsymmetric linear systems involves a Gram-Schmidt process which is a potential source of significant numerical error. An alternative implementation is outlined here in which orthogonalization by Householder transformations replaces the Gram-Schmidt process. Numerical experiments show that the new implementation is more stable.
文摘This paper describes a new method of QR-decomposition of square nonsingular matrices (real or complex) by the Givens rotations through the unitary discrete heap transforms. This transforms can be defined by a different path, or the order of processing components of input data, which leads to different realizations of the QR-decomposition. The heap transforms are fast, because of a simple form of decomposition of their matrices. The direct calculation of the N-point discrete heap transform requires no more than 5(N-1) multiplications, 2(N-1) additions, plus 3(N-1) trigonometric operations. The QR-decomposition of the square matrix N × N uses about 4/3N3 multiplications and N(N-1)/2 square roots. This number varies depending on the path of the heap transform, and it is shown that “the optimal path” allows for significant reduction of number of operations in QR-decomposition. The heap transform and its matrix can be described analytically, and therefore, this transform can also be applied to the QR-decomposition of complex matrices.
基金Supported by the National Natural Science Foundation of China(61473148)the Natural Science Foundation of Jiangsu Province of China(BK20141408)the Fundamental Research Funds for the Central Universities(NZ2014101)
基金This research was supported by Universiti Kebangsaan Malaysia under research grant GUP-2019-033.
文摘The classical iterative methods for finding roots of nonlinear equations,like the Newton method,Halley method,and Chebyshev method,have been modified previously to achieve optimal convergence order.However,the Householder method has so far not been modified to become optimal.In this study,we shall develop two new optimal Newton-Householder methods without memory.The key idea in the development of the new methods is the avoidance of the need to evaluate the second derivative.The methods fulfill the Kung-Traub conjecture by achieving optimal convergence order four with three functional evaluations and order eight with four functional evaluations.The efficiency indices of the methods show that methods perform better than the classical Householder’s method.With the aid of convergence analysis and numerical analysis,the efficiency of the schemes formulated in this paper has been demonstrated.The dynamical analysis exhibits the stability of the schemes in solving nonlinear equations.Some comparisons with other optimal methods have been conducted to verify the effectiveness,convergence speed,and capability of the suggested methods.
文摘In this papert we give a method to construct multivqriate wavelets for skewsymmetric scaling function. Such wavelets have some desirable properties, e,g.t they are real-valued and orthogonal if the scaling function is real-valued and orthonormalrespectively.
文摘A fast algorithm FBTQ is presented which computes the QR factorization a block-Toeplitz matrix A (A∈R) in O(mns3) multiplications. We prove that the QR decomposition of A and the inverse Cholesky decomposition can be computed in parallel using the sametransformation.We also prove that some kind of Toeplltz-block matrices can he transformed into the corresponding block-Toeplitz matrices.
文摘A fast Cholesky factorization algorithm based on the classical Schur algorithm for themp×mp symmetric positive definite (s. p. d) block-Toeplitz matrices is presented. The relation between the generator and the Schur complement of the matrices is explored. Besides, by applying the hyperbolic Householder transformations, we can reach an improved algorithm whose computational complexity is2p 2m3?4pm3+3/2m3+O(pm).
文摘Householder transform is used to triangularize the data matrix, which is basedon the near prediction error equation. It is proved that the sum of squared residuals for eachAR order can be obtained by the main diagonal elements of upper triangular matrix, so thecolumn by column procedure can be used to develop a recursive algorithm for AR modeling andspectral estimation. In most cases, the present algorithm yields the same results as the covariancemethod or modified covariance method does. But in some special cases where the numerical ill-conditioned problems are so serious that the covariance method and modified covariance methodfail to estimate AR spectrum, the presented algorithm still tends to keep good performance. Thetypical computational results are presented finally.
