Abstracts

 

Title:  Algebraic Properties and Preconditioning Methods for Block Two-by-Two Matrices
Zhongzhi Bai    Chinese Academy of Sciences

Abstract:  Large sparse systems of linear equations of block two-by-two coefficient matrices have plentiful application backgrounds in scientific computing and engineering applications. The standard and the generalized saddle point problems are their typical special cases. We discuss algebraic properties of the block two-by-two matrix, including nonsingularity, block-triangular factorizations, and eigenvalue estimates; provide algorithmic constructions of the block preconditioners and eigen-properties of the preconditioned matrices; and introduce effective approximations to the Schur complements. In addition, we address the augmented Lagrangian approach for designing the block-diagonal and block-triangular preconditioning matrices for application problems such as the discrete Navier-Stokes equations.

Title: Incremental Linear Discriminant Analysis

Delin Chu    National University of Singapore

Abstract: It has been a challenge problem to develop fast and efficient incremental linear discriminant analysis (LDA) algorithms although several incremental LDA algorithms have been proposed in the past. For this purpose, we conduct a new study on LDA and develop a new and efficient incremental LDA algorithm. We first propose a new batch LDA algorithm called LDA/QR which only depends on the data matrix and the sizes of data classes. LDA/QR is obtained by computing the economic QR factorization of the data matrix followed by solving a lower triangular linear system. Hence, LDA/QR is a simple and fast LDA algorithm. The relationship between LDA/QR and Uncorrelated LDA (ULDA) is also revealed. Based on LDA/QR, we develop a new incremental LDA algorithm called ILDA/QR which is the exact incremental version of LDA/QR.
The main features of our incremental LDA algorithm ILDA/QR include: (i) it can easily handle not only the case that only one new sample is inserted but also the case that a chunk of new samples are added; (ii) it has pleasant computational complexity and space complexity; and (iii) it is very fast and always achieves comparative classification accuracy compared with ULDA algorithm and existing incremental LDA algorithms. Numerical experiments using some real world data demonstrate that our ILDA/QR is very efficient and competitive with the state-of-the-art incremental LDA algorithms in terms of classification accuracy, computational complexity and space complexity.

Title:  Graphs associated with matrices over a finite field

Liping Huang  Changsha University of Science & Technology

Abstract: Let \mathbb{F} be a finite field. Let \mathbb{F}^{m\times n} be the set of m\times n matrices over \mathbb{F}, and {\mathcal K}_n  the set of all n\times n alternate matrices over \mathbb{F}, respectively. Consider a graph  G=(V,\sim), where vertex set V=\mathbb{F} ^{m\times n} (resp. {\mathcal K}_n), and A\sim B \Leftrightarrow rank (A-B)=1 (resp. 2) for all A,B\in V. We introduce some graph properties of graphs associated with m\times n matrices (resp. alternate matrices) over a finite field, they are: graph homomorphism, independence number, chromatic number, to distinguish Hamiltonian graph, to distinguish perfect graph, etc.

Title: Minimum rank solutions to the matrix approximation problems in spectral norm

Musheng Wei  Shanghai Normal University

Abstract: In this paper, we discuss the following two minimum rank matrix approximation problems in spectral norm: \min\limits_X \rank(X), subject to \|A-BXC\|_2=\theta, where   \theta \triangleq \min \limits_{Y} \|A-BYC\|_2; \min\limits_X\rank(X), subject to   \|A-BXC\|_2<\xi, where \xi >\theta . We solve the first problem by applying the norm-preserving dilation theorem and the restricted singular value decomposition (R-SVD) to characterize three expressions of the minimum rank, and derive general forms of minimum rank solutions. We also characterize the expressions of the minimum rank of the second problem, which is a generalization of the result in the literature.

Title: Recursion Theorem: from Liar’s paradox to computer virus

Guohua Wu  Nanyang Technological University

Abstract: Kleene’s Recursion Theorem is one of the most fundamental theorems in computability theory, which says that no computable function can be fixed-point free. In this talk, I will give an analysis of Kleene’s recursion theorem, from self-reference point of view, and show how people develop theoretical foundation of computer virology with recursion theorem as a basis.

Title: List decoding of Gabidulin codes

Chaoping Xing  Nangyang Technological University

Abstract: Gabidulin codes have found various applications in reliable communication of messages in linear network coding, crisscross error-correction in magnetic tape recording or memory chip arrays, space-time coding in wireless communications, public key cryptosystems. Despite this interest and many results paralleling Reed-Solomon codes, an algorithm for list decoding Gabidulin codes beyond half the distance has remained elusive. In this talk, we present a Monte Carlo construction of a Gabidulin code that is efficiently list decodable up to the Singleton bound.

Title: Galois Theory, Geometry and Coding

Jietai Yu  University of Hongkong

Abstract: In this talk we will explore the close connection among the classical Galois theory, geometry, camplex analysis and matrix theory via symmetry and representation, and possible applications in coding theory.

Title: Some efficient algorithms for skew polynomials

Yang Zhang  University of Manitoba

Abstract:  In this talk, we will outline some efficient algorithms for factoring skew polynomials and computing normal forms of matrices over skew polynomials, and describe some applications in cryptography, coding and control theory.

Title: DNA-like structure of nonlinear functions

Zhenyue Zhang  Zhejiang University

Abstract:  The importance of DNA to living organisms and its general structure of a double helix joined by base pairings whose sequences encode the genetic information are well known facts. Demonstrated in this article, via elementary calculus, is that there is a remarkably similar structure underneath all smooth nonlinear functions. The idea is based on generalizing the notion of gradient adaption from a scalar field to vector fields — singular vectors of the Jacobian of any given function form a moving frame pointing in directions along which the function changes most critically. Trajectories of these singular vectors, referred to as singular curves, unveil some interesting, perplexing, innate dynamics per the given function. At points where two or more singular values coalesce, curious and complex behavior occurs, manifesting specific landmarks for the underlying function. This talk reports for the first time such a dynamical system. For demonstration purpose only, the current study focuses primarily on the case of two-variable functions which, commonly used to characterize parametric surfaces, already exhibits some intriguing patterns. It is shown that, analogous to the double helix structure of DNA, two strands and eight base pairings could encode properties of an arbitrary surface.