On the Subspace Projected Approximate Matrix method

We provide a comparative study of the Subspace Projected Approximate Matrix method, abbreviated SPAM, which is a fairly recent iterative method of computing a few eigenvalues of a Hermitian matrix A. It falls in the category of inner-outer iteration methods and aims to reduce the costs of matrix-vector products with A within its inner iteration. This is done by choosing an approximation A ₀ of A, and then, based on both A and A ₀, to define a sequence (A _k ) _k=0 ⁿ of matrices that increasingly better approximate A as the process progresses. Then the matrix A _k is used in the kth inner iteration instead of A.In spite of its main idea being refreshingly new and interesting, SPAM has not yet been studied in detail by the numerical linear algebra community. We would like to change this by explaining the method, and to show that for certain special choices for A ₀, SPAM turns out to be mathematically equivalent to known eigenvalue methods. More sophisticated approximations A ₀ turn SPAM into a boosted version of Lanczos, whereas it can also be interpreted as an attempt to enhance a certain instance of the preconditioned Jacobi-Davidson method.Numerical experiments are performed that are specifically tailored to illustrate certain aspects of SPAM and its variations. For experiments that test the practical performance of SPAM in comparison with other methods, we refer to other sources. The main conclusion is that SPAM provides a natural transition between the Lanczos method and one-step preconditioned Jacobi-Davidson.     

Generalization of the Chinese remainder theorem

Sufficient conditions for a system Ax = r to have an integral solution in the case of a basic matrix A in terms of submatrices and permanents of A are derived. Matrix A in the Chinese remainder theorem is a particular case of a basic matrix. The derivation can be extended to the case where the propositional formula that describes the sign scheme of A is a minimal unsatisfiable CNF.     

Uniqueness theorem for linear elliptic equation of the second order with constant coefficients

The interior uniqueness theorem for analytic functions was generalized by M. B. Balk to the case of polyanalytic functions of order n. He proved that if the zeros of a polyanalytic function have an accumulation point of order n, then this function is identically zero. In this paper the interior uniqueness theorem is generalized to the solution to a linear homogeneous second order differential equation of elliptic type with constant coefficients.     

Some refined bounds for the perturbation of the orthogonal projection and the generalized inverse

In this paper, we consider the perturbation of the orthogonal projection and the generalized inverse for an n × n matrix A and present some perturbation bounds for the orthogonal projections on the rang spaces of A and A^?, respectively. A combined bound for the orthogonal projection on the rang spaces of A and A^? is also given. The proposed bounds are sharper than the existing ones. From the combined bounds of the orthogonal projection on the rang spaces of A and A^?, we derived new perturbation bounds for the generalized inverse, which always improve the existing ones. The combined perturbation bound for the orthogonal projection and the generalized inverse is also given. Some numerical examples are given to show the advantage of the new bounds.     

Factorization of cp-rank-3 completely positive matrices

A symmetric positive semi-definite matrix A is called completely positive if there exists a matrix B with nonnegative entries such that A = BB^?. If B is such a matrix with a minimal number p of columns, then p is called the cp-rank of A. In this paper we develop a finite and exact algorithm to factorize any matrix A of cp-rank 3. Failure of this algorithm implies that A does not have cp-rank 3. Our motivation stems from the question if there exist three nonnegative polynomials of degree at most four that vanish at the boundary of an interval and are orthonormal with respect to a certain inner product.     

On a recursive inverse eigenvalue problem

Let s ₁, ..., s _n be arbitrary complex scalars. It is required to construct an n × n normal matrix A such that s _i is an eigenvalue of the leading principal submatrix A _i , i = 1, 2, ..., n. It is shown that, along with the obvious diagonal solution diag(s ₁, ..., s _n ), this problem always admits a much more interesting nondiagonal solution A. As a rule, this solution is a dense matrix; with the diagonal solution, it shares the property that each submatrix A _i is itself a normal matrix, which implies interesting connections between the spectra of the neighboring submatrices A _i and A _{i + 1}.     

The classification of bi-quintic parametric polynomial minimal surfaces

Parametric polynomial surface is a fundamental element in CAD systems. Since the most of the classic minimal surfaces are represented by non-parametric polynomial, it is interesting to study the minimal surfaces represented in parametric polynomial form. Recently,Ganchev presented the canonical principal parameters for minimal surfaces. The normal curvature of a minimal surface expressed in these parameters determines completely the surface up to a position in the space. Based on this result, in this paper, we study the bi-quintic isothermal minimal surfaces. According to the condition that any minimal isothermal surface is harmonic,we can acquire the relationship of some control points must satisfy. Follow up, we obtain two holomorphic functions f(z) and g(z) which give the Weierstrass representation of the minimal surface. Under the constrains that the minimal surface is bi-quintic, f(z) and g(z) can be divided into two cases. One case is that f(z) is a constant and g(z) is a quadratic polynomial, and another case is that the degree of f(z) and g(z) are 2 and 1 respectively. For these two cases,we transfer the isothermal parameter to canonical principal parameter, and then compute their normal curvatures and analyze the properties of the corresponding minimal surfaces. Moreover,we study some geometric properties of the bi-quintic harmonic surfaces based on the B′ezier representation. Finally, some numerical examples are demonstrated to verify our results.     

Restarted Q-Arnoldi-type methods exploiting symmetry in quadratic eigenvalue problems

We investigate how to adapt the Q-Arnoldi method for the case of symmetric quadratic eigenvalue problems, that is, we are interested in computing a few eigenpairs \((\lambda ,x)\) of \((\lambda ^2M+\lambda C+K)x=0\) with M, C, K symmetric \(n\times n\) matrices. This problem has no particular structure, in the sense that eigenvalues can be complex or even defective. Still, symmetry of the matrices can be exploited to some extent. For this, we perform a symmetric linearization \(Ay=\lambda By\), where A, B are symmetric \(2n\times 2n\) matrices but the pair (A, B) is indefinite and hence standard Lanczos methods are not applicable. We implement a symmetric-indefinite Lanczos method and enrich it with a thick-restart technique. This method uses pseudo inner products induced by matrix B for the orthogonalization of vectors (indefinite Gram-Schmidt). The projected problem is also an indefinite matrix pair. The next step is to write a specialized, memory-efficient version that exploits the block structure of A and B, referring only to the original problem matrices M, C, K as in the Q-Arnoldi method. This results in what we have called the Q-Lanczos method. Furthermore, we define a stabilized variant analog of the TOAR method. We show results obtained with parallel implementations in SLEPc.     

Globally convergent Jacobi methods for positive definite matrix pairs

The paper derives and investigates the Jacobi methods for the generalized eigenvalue problem A x = λ B x, where A is a symmetric and B is a symmetric positive definite matrix. The methods first “normalize” B to have the unit diagonal and then maintain that property during the iterative process. The global convergence is proved for all such methods. That result is obtained for the large class of generalized serial strategies from Hari and Begovi? Kova? (Trans. Numer. Anal. (ETNA) 47, 107–147, 2017). Preliminary numerical tests confirm a high relative accuracy of some of those methods, provided that both matrices are positive definite and the spectral condition numbers of Δ _A AΔ _A and Δ _B BΔ _B are small, for some nonsingular diagonal matrices Δ _A and Δ _B .     

The real symmetric matrices of odd order with a P-set of maximum size

Suppose that A is a real symmetric matrix of order n. Denote by m_A(0) the nullity of A. For a nonempty subset α of {1, 2,..., n}, let A(α) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α. When m_A(α)(0) = m_A(0)+|α|, we call α a P-set of A. It is known that every P-set of A contains at most ?n/2? elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As a first step to the full characterization of these graphs of odd order, we establish some conditions for such graphs G under which there is a real symmetric matrix A whose graph is G and contains a P-set of size (n ? 1)/2.     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

On the commutation graph of cyclic <Emphasis Type="Italic">TI</Emphasis>-subgroups in linear groups

We study the commutation graph Γ(A) of a cyclic TI-subgroup A of order 4 in a finite group G with quasisimple generalized Fitting subgroup F*(G). It is proved that, if F*(G) is a linear group, then the graph Γ(A) is either a coclique or an edge-regular graph but not a coedge-regular graph.     

A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows

The effectiveness of sparse matrix techniques for directly solving large-scale linear least-squares problems is severely limited if the system matrix A has one or more nearly dense rows. In this paper, we partition the rows of A into sparse rows and dense rows (A_s and A_d) and apply the Schur complement approach. A potential difficulty is that the reduced normal matrix AsTA_s is often rank-deficient, even if A is of full rank. To overcome this, we propose explicitly removing null columns of A_s and then employing a regularization parameter and using the resulting Cholesky factors as a preconditioner for an iterative solver applied to the symmetric indefinite reduced augmented system. We consider complete factorizations as well as incomplete Cholesky factorizations of the shifted reduced normal matrix. Numerical experiments are performed on a range of large least-squares problems arising from practical applications. These demonstrate the effectiveness of the proposed approach when combined with either a sparse parallel direct solver or a robust incomplete Cholesky factorization algorithm.     

On the complexity of generalized polynomials of <Emphasis Type="Italic">k</Emphasis>-valued functions

Specification of k-valued functions with generalized polynomials (for simple k) is considered. A generalized polynomial is a mod k polynomial in which each variable may also occur with one or several Post negations. The upper and lower estimates of the complexity of generalized polynomials are found for k-valued functions.     

The complete reducibility of some <Emphasis Type="Italic">GF</Emphasis>(2)<Emphasis Type="Italic">A</Emphasis><Subscript>7</Subscript>-modules

It is proved that, if G is a finite group with a nontrivial normal 2-subgroup Q such that G/Q ～= A ₇ and an element of order 5 from G acts freely on Q, then the extension G over Q is splittable, Q is an elementary abelian group, and Q is the direct product of minimal normal subgroups of G each of which is isomorphic, as a G/Q-module, to one of the two 4-dimensional irreducible GF(2)A ₇-modules that are conjugate with respect to an outer automorphism of the group A ₇.     

G-matrices,J-orthogonal matrices,and their sign patterns

A real matrix A is a G-matrix if A is nonsingular and there exist nonsingular diagonal matrices D₁ and D₂ such that A^?T = D₁AD₂, where A^?T denotes the transpose of the inverse of A. Denote by J = diag(±1) a diagonal (signature) matrix, each of whose diagonal entries is +1 or ?1. A nonsingular real matrix Q is called J-orthogonal if Q^TJQ = J. Many connections are established between these matrices. In particular, a matrix A is a G-matrix if and only if A is diagonally (with positive diagonals) equivalent to a column permutation of a J-orthogonal matrix. An investigation into the sign patterns of the J-orthogonal matrices is initiated. It is observed that the sign patterns of the G-matrices are exactly the column permutations of the sign patterns of the J-orthogonal matrices. Some interesting constructions of certain J-orthogonal matrices are exhibited. It is shown that every symmetric staircase sign pattern matrix allows a J-orthogonal matrix. Sign potentially J-orthogonal conditions are also considered. Some examples and open questions are provided.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

Theoretical basis of the iterative process of the joint assessment of difficulties in tasks and levels of training students

In this paper, we study the iterative process of the joint numerical assessment of levels of training students and difficulties in tasks of diagnostic tools using the dichotomous response matrix A of size N × M with allowance for the contribution of tasks of different difficulty to the assessments obtained. It is shown that not for any matrix A there exist infinite iterative sequences, and in the case of their existence, they do not always converge. A wide range of sufficient conditions for their convergence have been obtained, which are based on the following: (1) the matrix A contains at least three different columns; (2) if one places the columns of the matrix A in non-decreasing order of column sums, then for any position of the vertical dividing line between the columns there exists a row, which has at least one unity to the left of the line and at least one zero to the right of the line. It is established that the response matrix A obtained as a result of testing reliability satisfies these two conditions. The properties of such matrices have been studied. In particular, the equivalence of the above-mentioned conditions of primitiveness of the square matrix B of order M with the entries \({b_{ij}} = \sum\limits_{\ell = 1}^N {(1 - {a_{\ell i}}){a_{\ell i}}} \) has been proved. Using the matrix analysis, we have proved that the primitiveness of the matrix B ensures the convergence of iterative sequences, as well as independence of their limits of the choice of the initial approximation. We have estimated the rate of convergence of these sequences and found their limits.     

Comparing the <Emphasis Type="Italic">ℤ</Emphasis><Subscript>2</Subscript>-Graded Identities of Two Minimal Superalgebras with the Same Superexponent

Let F be a field of characteristic zero. We study two minimal superalgebras A and B having the same superexponent but such that T ₂ (A) ? T ₂ (B), thus providing the first example of a minimal superalgebra generating a non minimal supervariety. We compare the structures and codimension sequences of A and B.