Analyzing games by Boolean matrix iteration

Finite win-draw-lose games with perfect information are studied, using a Boolean formulation with the intention of computational realization. The interdependence of the sets of winning strategies is expressed by means of Boolean matrix equations. Their solutions which describe the winning positions can be obtained by matrix iteration. In the case of last-player-winning games this method shows the existence of two kernels of a bipartite graph which are distinguished in the sense that they bound all other possible kernels. For some chess endings with three and four men all positions are completely analyzed.     

A Boolean algebra and a Banach space obtained by push-out iteration

Under the assumption that c is a regular cardinal, we prove the existence and uniqueness of a Boolean algebra B of size c defined by sharing the main structural properties that P(ω)/fin has under CH and in the ℵ₂-Cohen model. We prove a similar result in the category of Banach spaces.     

Projected Landweber iteration for matrix completion

Recovering an unknown low-rank or approximately low-rank matrix from a sampling set of its entries is known as the matrix completion problem. In this paper, a nonlinear constrained quadratic program problem concerning the matrix completion is obtained. A new algorithm named the projected Landweber iteration (PLW) is proposed, and the convergence is proved strictly. Numerical results show that the proposed algorithm can be fast and efficient under suitable prior conditions of the unknown low-rank matrix.     

二元Boolean矩阵的加权Moore-Penrose逆

主要研究了二元Boolean矩阵A的加权Moore-Penrose逆的存在性问题,给出了二元Boolean矩阵A的加权Moore-Penrose逆存在的一些充分必要条件,并讨论了加权Moore-Penrose逆存在时的若干等价刻画及惟一性问题.     

Simultaneous iteration for the matrix eigenvalue problem

Let B be a given positive definite Hermitian matrix, and assume the matrix P satisfies the “normality” condition PB^?1P^HB=B^?1P^HBP, where P^H denotes the Hermitian of P. In this paper, we develop an accelerated version of simultaneous iteration for partial solution of the eigenproblem Px=λx. Convergence together with sharp error bounds is obtained. The results are then applied to the solution of the symmetric eigenproblem Ax=λBx, where the algorithms are shown to be improvements over existing techniques.     

用迭代方法解一类特殊的矩阵方程

本主要研究解矩阵方程AX YB=D和AX XB=D的一种迭代方法．     

On the complexity of Boolean matrix ranks

We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute.     

A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems

Numerical Algorithms - In this paper, for solving horizontal linear complementarity problems, a two-step modulus-based matrix splitting iteration method is established. The convergence analysis of...     

A modified modulus-based matrix splitting iteration method for solving implicit complementarity problems

In this paper, a modified modulus-based matrix splitting iteration method is established for solving a class of implicit complementarity problems. The global convergence conditions are given when the system matrix is a positive definite matrix or an H₊-matrix, respectively. In addition, some numerical examples show that the proposed method is efficient.

     

A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems

In this paper, a relaxation modulus-based matrix splitting iteration method is established, which covers the known general modulus-based matrix splitting iteration methods. The convergence analysis and the strategy of the choice of the parameters are given. Numerical examples show that the proposed methods are efficient and accelerate the convergence performance with less iteration steps and CPU times.     

On the parameter selection in the transformed matrix iteration method

Numerical Algorithms - Recently, Axelsson and Salkuyeh in (BIT Numerical Mathematics, 59 (2019) 321–342) proposed the transformed matrix iteration (TMIT) method for solving a certain...     

Multistep matrix splitting iteration preconditioning for singular linear systems

Multistep matrix splitting iterations serve as preconditioning for Krylov subspace methods for solving singular linear systems. The preconditioner is applied to the generalized minimal residual (GMRES) method and the flexible GMRES (FGMRES) method. We present theoretical and practical justifications for using this approach. Numerical experiments show that the multistep generalized shifted splitting (GSS) and Hermitian and skew-Hermitian splitting (HSS) iteration preconditioning are more robust and efficient compared to standard preconditioners for some test problems of large sparse singular linear systems.     

求解Sylvester矩阵方程的一种改进的梯度方法

提出了一种改进的梯度迭代算法来求解Sylvester矩阵方程和Lyapunov矩阵方程.该梯度算法是通过构造一种特殊的矩阵分裂,综合利用Jaucobi迭代算法和梯度迭代算法的求解思路.与已知的梯度算法相比,提高了算法的迭代效率.同时研究了该算法在满足初始条件下的收敛性.数值算例验证了该算法的有效性.     

Two-step modulus-based matrix splitting iteration methods for retinex problem

Numerical Algorithms - Retinex theory was proposed by Land in the 1970s. Its theoretical basis is that the color of an object is determined by the reflection ability of the object to the light of...     

A bound on the scrambling index of a primitive matrix using Boolean rank

The scrambling index of an n×n primitive matrix A is the smallest positive integer k such that A^k(A^t)^k=J, where A^t denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M=AB for some m×b Boolean matrix A and b×n Boolean matrix B. In this paper, we give an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M). Furthermore we characterize all primitive matrices that achieve the upper bound.     

Convergence of projected Landweber iteration for matrix rank minimization

In this paper, we study the performance of the projected Landweber iteration (PLW) for the general low rank matrix recovery. The PLW was first proposed by Zhang and Chen (2010) [43] based on the sparse recovery algorithm APG (Daubechies et al., 2008) [14] in the matrix completion setting, and numerical experiments have been given to show its efficiency (Zhang and Chen, 2010) [43]. In this paper, we focus on providing a convergence rate analysis of the PLW in the general setting of low rank matrix recovery with the affine transform having the matrix restricted isometry property. We show robustness of the algorithm to noise with a strong geometric convergence rate even for noisy measurements provided that the affine transform satisfies a matrix restricted isometry property condition.