Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation

This paper presents a new algorithm for computing the maximum degree δk (A) of a minor of order k in a matrix pencil A(s) . The problem is of practical significance in the field of numerical analysis and systems control. The algorithm adopts a general framework of ``combinatorial relaxation'' due to Murota. It first solves the weighted bipartite matching problem to obtain an estimate $\hat{\delta}_k(A)$ on δk (A) , and then checks if the estimate is correct, exploiting the optimal dual solution. In case of incorrectness, it modifies the matrix pencil A(s) to improve the estimate $\hat{\delta}_k(A)$ without changing δk(A) . The present algorithm performs this matrix modification by an equivalence transformation with constant matrices, whereas the previous one uses biproper rational function matrices. Thus the present approach saves memory space and reduces the running time bound by a factor of rank A.     

Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation

Mixed polynomial matrices are polynomial matrices with two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. The computation of their maximum degrees of minors is known to be reducible to valuated independent assignment problems, which can be solved by polynomial numbers of additions, subtractions, and multiplications of rational functions. However, these arithmetic operations on rational functions are much more expensive than those on constants. In this paper, we present a new algorithm of combinatorial relaxation type. The algorithm finds a combinatorial estimate of the maximum degree by solving a weighted bipartite matching problem, and checks if the estimate is equal to the true value by solving independent matching problems. The algorithm mainly relies on fast combinatorial algorithms and performs numerical computation only when necessary. In addition, it requires no arithmetic operations on rational functions. As a byproduct, this method yields a new algorithm for solving a linear valuated independent assignment problem.     

EXCEL在矩阵相关计算中的应用

Excd不但具有强大的数据分析和处理功能，而且具有丰富的函数，在数学计算中发挥着不客忽视的作用。本文主要介绍Excel在进行计算行列式值、矩阵的转置、矩阵的逆、矩阵的秩、两矩阵的乘积、矩阵的特征向量和特征值以及矩阵在进行解线性方程组时的应用。     

The Role of Arithmetic in Fast Parallel Matrix Inversion

In the last two decades several NC algorithms for solving basic linear algebraic problems have appeared in the literature. This interest was clearly motivated by the emergence of a parallel computing technology and by the wide applicability of matrix computations. The traditionally adopted computation model, however, ignores the arithmetic aspects of the applications, and no analysis is currently available demonstrating the concrete feasibility of many of the known fast methods. In this paper we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically brilliant solutions fail the severe test of the ``Engineering of Algorithms.' We perform a comparative analysis of several well-known numerical matrix inversion algorithms under both fixed- and variable-precision models of arithmetic. We show that, for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-arithmetic setting no benefit derives from conditions usually deemed favorable in standard scientific computing. Under these circumstances, the only algorithm admitting sufficiently accurate NC implementations is Newton's iterative method, and the word size required to guarantee worst-case correctness appears to be the critical complexity measure. Our analysis also accounts for the observed instability of the considered superfast methods when implemented with the same floating-point arithmetic that is perfectly adequate for the fixed-precision approach. Received March 28, 1998; revised February 2, 1999, and April 21, 1999.     

Matrix pencil method for simultaneously estimating azimuth and elevation angles of arrival along with the frequency of the incoming signals

In this paper we describe a method for simultaneously estimating the direction of arrival (DOA) of the signal along with its unknown frequency. In a typical DOA estimation problem it is often assumed that all the signals are arriving at the antenna array at the same frequency which is assumed to be known. The antenna elements in the array are then placed half wavelength apart at the frequency of operation. However, in practice seldom all the signals arrive at the antenna array at a single pre-specified frequency, but at different frequencies. The question then is what to do when there are signals at multiple frequencies, which are unknown. This paper presents an extension of the matrix pencil method to simultaneously estimate the DOA along with the operating frequency of each of the signals. This novel approach involves approximating the voltages that are induced in a three-dimensional antenna array, by a sum of complex exponentials by jointly estimating the direction of arrival (both azimuth and elevation angles) along with the carrier frequencies of multiple far-field sources impinging on the array by using the three-dimensional matrix pencil method. The matrix pencil method is a direct data domain method for approximating a function by a sum of complex exponentials in the presence of noise. The variances of the estimates computed by the matrix pencil method are quite close to the Cramer–Rao bound. Finally, we illustrate how to carry out the broadband DOA estimation procedure using realistic antenna elements located in a conformal array. Some numerical examples are presented to illustrate the applicability of this methodology in the presence of noise. It is shown that the variance decreases as the SNR increases. The Cramer–Rao bound for the estimators are also provided to illustrate the accuracy and the computational efficiency of this new methodology.     

双因素等重复试验方差分析的矩阵求解方法

矩阵是对对应成组的多数据问题进行处理的有利工具,统计分析是对多数据问题进行分析的重要方法,两者结合,为统计分析提供了新的工具,为矩阵拓展了应用范围.本文给出了双因素等重复试验的方差分析的矩阵求解方法.     

Expansion in Terms of Power of a Small Parameter of the Maximum Rank Distribution of a Random Boolean Matrix

The paper considers an N × n matrix (N n) over a field GF(2) that consists of random values with a distribution depending on a small parameter . The expansion is found in terms of the power of the parameter of the probability that the matrix rank is equal to n. Exact values of the first three coefficients are indicated.     

Thermodynamics of martensitic transformations in the framework of the CALPHAD approach

Martensitic phases occur in a number of metallic materials, and are metastable in many systems. They have been of significant importance in steels for a long time, and have generated a great interest in Shape Memory Alloys (SMA) in recent years. This review describes a thermodynamic and kinetic approach for modelling martensitic phases in the framework of the CALPHAD approach.