Opportunities and Challenges in Numerical Algebra

Numerical algebra has played a pivotal role as the backbone of scientific computing for decades. Theories and numerical techniques for its core problems, including linear systems, least squares problems, and eigenvalue problems, are taken for granted and widely used in science and engineering. Today, thanks to the advent of data science and artificial intelligence, numerical algebra is at a crossroads in transforming itself to adapt to a rapidly changing environment. This half-day online workshop series aims to bring you a series of advanced technical talks on the latest developments in numerical algebra and its recent machine-learning applications.

1. 2021/01/27

• Junfeng Yin (Tongji University)

1. Title: Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems

2. Abstract: We propose using greedy and randomized Kaczmarz inner-iterations as preconditioners for the right-preconditioned flexible GMRES method to solve consistent linear systems, with a parameter tuning strategy for adjusting the number of inner iterations and the relaxation parameter. We also present theoretical justifications of the right- preconditioned flexible GMRES for solving consistent linear systems. Numerical experiments on overdetermined and underdetermined linear systems show that the proposed method is superior compared to the GMRES method preconditioned by NE- SOR inner iterations in terms of total CPU time. This work is cooperated with Du Yishu, Hayami Ken, Zheng Ning, Morikuni Keiichi.

• Li Wang (University of Texas at Arlington)

1. Title: Probabilistic Semi-supervised Learning via Sparse Graph Structure Learning

2. Abstract: We present a probabilistic semi-supervised learning (SSL) framework based on sparse graph structure learning. Different from existing SSL methods with either a predefined weighted graph heuristically constructed from the input data or a learned graph based on the locally linear embedding assumption, the proposed SSL model is capable of learning a sparse weighted graph from the unlabeled high-dimensional data and a small amount of labeled data, as well as dealing with the noise of the input data. Our representation of the weighted graph is indirectly derived from a unified model of density estimation and pairwise distance preservation in terms of various distance measurements, where latent embeddings are assumed to be random variables following an unknown density function to be learned and pairwise distances are then calculated as the expectations over the density for the model robustness to the data noise. Moreover, the labeled data based on the same distance representations is leveraged to guide the estimated density for better class separation and sparse graph structure learning. A simple inference approach for the embeddings of unlabeled data based on point estimation and kernel representation is presented. Extensive experiments on various data sets show the promising results in the setting of SSL compared with many existing methods, and significant improvements on small amounts of labeled data.

• Ding Lu (University of Kentucky)

1. Title: Subspace Methods for Hermitian Eigenvalue Optimization

2. Abstract: Many optimization problems over the numerical range of a matrix lead to minimization of the largest eigenvalue of a Hermitian matrix that depends on one parameter. Two common examples are Crawford number computation and max-ratio minimization. We present two projection-based subspace methods for such problems: one uses eigenvector sampling, and the other uses local subspace searching with gradients. We discuss the convergence of both algorithms and demonstrate their performance by examples with applications.

• Leihong Zhang (Soochow University)

1. Title: A structure-exploiting nested Lanczos-type iteration for the multi-view canonical correlation analysis

2. Abstract: Data points from many recent real applications usually have the multi-view structure in the sense that they are drawn from a multivariate random variable $v\in \mathbb{R}^n$ that can be partitioned into multiple, say $m$, sub-variables (i.e., multi-view) ${v}_i\in\mathbb{R}^{n_i}$ for $i=1,\ldots,m$ and $\sum_{i=1}^mn_i=n$. The multi-view canonical correlation analysis is a statistical approach which fuses each sub-variables $v_i$ into a reduced one $s_i=x_i^{T}{v}_i$ through a linear combination ${x}_i$ so that the fused $m$ random variables achieve the maximum of a certain type of correlation. Among many criteria that measure the correlation, one of the earliest rules is to maximize the sum of all pairwise-correlations subject to the ellipsoidal constraint of each ${x}_i$, which is commonly referred to as MCP. Existing methods for MCP may encounter slow convergence or inapplicable in the applications with high-dimensional features. In this talk, we propose a Krylov subspace type method by exploiting the special structure of the ellipsoidal constraint of ${x}_i$. Convergence will be discussed and numerical demonstration of the efficiency is reported on an application of the unsupervised feature fusion with real data.

2. 2021/02/03

• Shih-Feng Shieh (National Taiwan Normal University)

1. Title: The orthogonal flows for orthogonal iteration

2. Abstract: In the field of scientific computation, the orthogonal iteration plays an essential role in computing the invariant subspace corresponding to the largest $k$ eigenvalues. In this paper, we construct a flow that connects the sequence of matrices generated by the orthogonal iteration. Such a flow is called an orthogonal flow. Besides, we also show that the orthogonal iteration forms a time-one mapping of the orthogonal flow. By using a suitable change of variables, the orthogonal flow can be transformed into a Riccati differential equation (RDE). Conversely, an RDE also can be transformed into a flow that can be represented by the orthogonal flow multiplied by an orthogonal matrix.

• Yuanzhe Xi (Emory University)

1. Title: Data-driven hierarchical kernel matrix methods

2. Abstract: The explosion of datasets from diverse applications and the increasing computational power of computer hardware call for the need of scalable algorithms and software. In this talk, I will focus on the computational bottlenecks associated with fully populated kernel matrices that are ubiquitous in machine learning as well as scientific simulations. Those dense matrices usually induce large computation costs that scale quadratically or cubically with problem size. The complexity can be significantly reduced by exploiting the hierarchical rank structure inside the kernel matrices. Representing a kernel matrix in an appropriate hierarchical format enables (nearly) optimal storage and computations. I will demonstrate the newly developed data-driven techniques for hierarchical representations and compare their performance with state-of-the-art methods/software on several real-world applications.

• Matthew M. Lin (National Cheng Kung University)

1. Title: Analytics for Information Retrieval for structured low-rank matrix

2. Abstract: Recovering a structured low-rank matrix nearest to a given matrix is an essential but challenging task. Its work is to retrieve valuable information from a dataset while keeping the desired physical structure. This talk addresses two types of low-rank approximation associated with discrete type datasets and quantum physics with rigorous convergence analysis. Applications include cluster analysis, pattern discovery, and quantum entanglement. Compared with state-of-the-art optimization techniques, our proposed procedures, despite the simplicity, are more efficient and accurate. These methods might serve as a building block for any other low-rank approximation with more complicated structures.

• Lulu Liu (Nanjing University of Science and Technology)

1. Title: Adaptive Nonlinear Preconditioning Techniques

2. Abstract: Nonlinear preconditioning is a globalization technique for Newton’s method applied to systems of equations with unbalanced nonlinearities, in which nonlinear residual norm reduction stagnates due to slowly evolving subsets of the degrees of freedom. Even though the Newton corrections may effectively be sparse, a standard Newton method still requires large ill-conditioned linear systems resulting from global linearizations of the nonlinear residual to be solved at each step. Nonlinear preconditioners may enable faster global convergence by shifting work to where it is most strategic, on subsets of the original system. They require additional computation per outer iteration while aiming for many fewer outer iterations and correspondingly fewer global synchronizations. In this work, we improve upon previous nonlinear preconditioning implementations by introducing parameters that allow turning off nonlinear preconditioning during outer Newton iterations where it is not needed. Numerical experiments show that the adaptive nonlinear preconditioning algorithm has performance similar to monolithically applied nonlinear preconditioning, preserving robustness for some challenging problems representative of several PDE-based applications while saving work on nonlinear subproblems.

3. 2021/02/17

• Shih Yu Chang (San Jose State University)

1. Title: Tensor Perturbation and Its Applications

2. Abstract: Data perturbation is deemed a common problem in data processing. It is often inevitable to avoid noisy or misleading data which may arise from real-world collection or model imprecision. Besides, when data privacy is concerned, data perturbation is used as a prevalent data-protection approach, which alters individual data in a way such that the summary statistics still remain more or less the same. Since many data-mining problems can be formulated as tensor equations for characterizing multi-relational data, the main focus of this work is to perform a new perturbation analysis of tensor equations. In this work, new theorems are first introduced to quantify the normalized error-norm of the solution to an arbitrary invertible tensor equation with respect to perturbation degree and tensor condition number. Second, we generalize the Sherman–Morrison–Woodbury identity for tensor with Moore-Penrose inverse and apply this new tensor identity to characterize the error bound for the solution of a multilinear system between the original system and the corrected system. Finally, a pertinent data-processing application, namely information retrieval, is also presented to illustrate how one can utilize this new tensor perturbation analysis with real-world (web) data collected for typical information retrieval tasks.

• Weiguo Gao (Fudan University)

1. Title: New Algorithms for Eigenvalue Calculations

2. Abstract: In this talk I will present my collaborative work on new algorithms for solving two different types of eigenvalue problems. Firstly, a novel orthogonalization-free method together with two specific algorithms are proposed to solve extreme eigenvalue problems. These algorithms achieve eigenvectors instead of eigenspace. Global convergence and local linear convergence are discussed. Efficiency of new algorithms are demonstrated on random matrices and matrices from computational chemistry. Secondly, we explore the possibility of using a reinforcement learning (RL) algorithm to solve large-scale k-sparse eigenvalue problems. By describing how to represent states, actions, rewards and policies, an RL algorithm is designed and demonstrated the effectiveness on examples from quantum many-body physics.

• Junjun Pan (University of Hong Kong) (潘珺珺, 香港大學)

1. Title: Generalized Separable Nonnegative Matrix Factorization

2. Abstract: Nonnegative matrix factorization (NMF) is a linear dimensionality technique for nonnegative data with applications such as image analysis, text mining, audio source separation and hyperspectral unmixing. Given a data matrix M and a factorization rank r, NMF looks for a nonnegative matrix W with r columns and a nonnegative matrix H with r rows such that M ≈ WH. NMF is NP-hard to solve in general. However, it can be computed efficiently under the separability assumption which requires that the basis vectors appear as data points, that is, that there exists an index set K such that W = M (:, K). In this paper, we generalize the separability assumption: We only require that for each rank-one factor W (:, k) H (k , :) for k=1,2,…,r, either W(:,k) = M(:,j) for some j or H(k,:) = M(i,:) for some i. We refer to the corresponding problem as generalized separable NMF (GS-NMF). We discuss some properties of GS-NMF and propose a convex optimization model which we solve using a fast gradient method. We also propose a heuristic algorithm inspired by the successive projection algorithm. To verify the effectiveness of our methods, we compare them with several state-of-the-art separable NMF and standard NMF algorithms on synthetic, document and image data sets.

4. 2021/02/24

• Bo Yu (Dalian University of Technology)

1. Title: Results on Portfolio Optimization: Model, Theory and Algorithms

2. Abstract: In this talk, I will give a brief introduction to our recent works on portfolio optimization. At first, a new distributionally robust modeling strategy based on kernel density estimation will be introduced, tractable reformulation of KDE distributionally robust portfolio optimization models, with CVaR, EVaR and HMCR as risk measures respectively, will be shown. Then some efficient algorithms for solving sparse portfolio optimization as well as their convergence will be introduced. Numerical results will also be given to show good performance of our new models and efficiency of our new algorithms.

• Limin Li (Xi'an Jiaotong University) (李麗敏，西安交通大學)

1. Title: Numerical algebra in biological data analysis

2. Abstract: Numerical algebra plays a very important role in biological data analysis, since biological data are often represented as matrices, for example, gene expression data and protein-protein interaction networks. In this talk, I will present several problems in biological data analysis, including multi-omics data integration and cross-species study. The models for solving these problems can be finally boiled down to problems in numerical algebra, such as matrix decomposition, optimization in Grassmann manifold or nonlinear eigenvalue problem. We gave some theoretical analysis for the problems and also proposed numerical algorithms for solving these problems. Finally, some experimental results were shown to evaluate the methods.

• Yingzhou Li (Fudan University)

1. Title: Tensor Ring Decomposition

2. Abstract: We study the tensor ring decomposition and its associated numerical algorithms. We establish a sharp transition of algorithmic difficulty of the optimization problem as the bond dimension increases: On one hand, we show the existence of spurious local minima for the optimization landscape even when the tensor ring format is much overparameterized, i.e., with bond dimension much larger than that of the true target tensor. On the other hand, when the bond dimension is further increased, we establish one-loop convergence for the alternating least squares algorithm for the tensor ring decomposition. The theoretical results are complemented by numerical experiments for both local minima and the one-loop convergence for the alternating least squares algorithm.

1. 2021/03/20

• Pengwen Chen (National Chung Hsing University)

1. Title: Arnoldi Algorithms with Structured Orthogonalization

2. Abstract: We study a stability preserved Arnoldi algorithm for matrix exponential in the time domain simulation of large-scale power delivery networks (PDNs), which are formulated as semi-explicit differential algebraic equations (DAEs). The solution can be decomposed to a sum of two projections, one in the range of the system operator and the other in its null space. The range projection can be computed with a shift-and-invert Krylov subspace method. The other projection can be computed with the algebraic equations. Differing from the ordinary Arnoldi method, the orthogonality in the Krylov subspace is replaced with the semi-inner product induced by the positive semidefinite system operator. With proper adjustment, numerical ranges of the Krylov operator lie in the right half-plane, and we obtain theoretical convergence analysis for the modified Arnoldi algorithm in computing phi-functions. Last, simulations on RLC networks are demonstrated to validate the effectiveness of the Arnoldi algorithm.

• Hehu Xie (Chinese Academy of Sciences) (謝和虎, 中國科學院)

1. Title: Augmented subspace algorithm for eigenvalue problem and its application

2. Abstract: This report first introduces the basic algorithms for solving eigenvalue problems and the corresponding error estimates, and then constructs the augmented subspace algorithm for solving eigenvalue problems combined with the characteristics of finite element discretization. Next, the augmented subspace algorithm and multi-level are used to construct a multi-level correction algorithm for solving eigenvalue problems. In addition, some applications and usage of the augmented subspace algorithm in other problems will be introduced.

• Xin Liang (Tsinghua University)

1. Title: On the Optimality of the Oja-Karhunen Algorithm for Online Principal Subspace Estimation

2. Abstract: Principal component analysis (PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA, (subspace) online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of (subspace) online PCA iterations mostly focus on the case where sample are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumption and obtain an optimal finite-sample error bound up to a constant factor.  Our convergence rate matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses.

2. 2021/03/27

• Zhiqiang Xu (Chinese Academy of Sciences) (許志強, 中國科學院)

1. Title: Phase retrieval: theory, model and algorithm

2. Abstract: We consider the numerical solution of large-scale M-matrix algebraic Riccati equations (MAREs) with low-rank structures. We derive a new doubling iteration, decoupling the four original iteration formulae in the alternating-directional doubling algorithm. We prove that the kernels in the decoupled algorithm are small M-matrices. Illumined by the highly accurate algorithm proposed by Xue and Li in 2017, we construct the novel triplet representations for the small M-matrix kernels in a highly accurate doubling algorithm. With these triplet representations, we develop a highly accurate doubling algorithm, named dADDA, for large-scale MAREs with low-rank structures, where the GTH-like algorithm is applied for solving the associated linear systems. Illustrative numerical examples will be presented on the efficiency of our algorithm.

• Xile Zhao (University of Electronic Science and Technology of China) (趙熙樂, 電子科技大學)

1. Title: Low-Rank Tensor Completion (LRTC) Problem: When Model-Driven Method Meets Data-Driven Method

2. Abstract: Phase retrieval and matrix recovery have been proposed in many application problems and become a hot topic in applied mathematics and computational mathematics. The following three problems are proposed in the field of pure mathematics: nonsingular bilinear form, embedding of complex projective space in Euclidean space and dimension of algebraic cluster. These problems also have a long history in mathematics. For example, the first nontrivial result of nonsingular bilinear form was discovered by Euler when he tried to prove Fermat's last theorem in 1748. In the report, we will see that the phase retrieval and matrix recovery driven by application problems and the above three problems driven by interest are actually different aspects of the same problem. We will introduce their connection and get some new results from it. Nonlinear least squares model is a popular model in phase retrieval. A lot of algorithms have been designed to solve the problem, but little is known about the performance of the model. We will introduce our work on the performance of the model and new algorithm.

• Zhenchen Guo (Nanjing University)

1. Title: Highly accurate decoupled doubling algorithm for large-scale M-matrix algebraic Riccati equations

2. Abstract: Recently, the tensor completion problem, which recovers the underlying tensor from partially observed multi-dimensional data, has received great attention. However, only considering the deterministic low-rank prior is not enough sometimes for missing multi-dimensional data recovery, especially for complex and realistic scenarios. In this talk, we will discuss the model-driven and data-driven methods for the tensor completion problem by fully exploring global prior, nonlocal prior, and local prior knowledge. Extensive numerical examples of synthetic and real data are delivered to demonstrate the superiority of the proposed methods over state-of-the-art methods.

1. 2022/04/09

• Mufa Chen (Jiangsu Normal University) (陳木發, 江蘇師範大學)

1. Title: New Skills of Matrix Computation

2. Abstract: The talk starts at an isospectral transformation: reducing the almost-nonnegative matrix to a transition probability matrix. It is an essential tool now in the study of economy. For leveling the elements of matrix or its maximal eigenvector, the symmetrizing and the first/second quasi-symmetrizing techniques are introduced for computing the maximal eigenpair. For large scale matrix, a mixed algorithm of three classical algorithms is shortly introduced. A specific coupling technique for computing the maximal eigenpair for tridiagonal matrix is also discussed, in which case, the algorithm is O(N). Finally, as an extension of the above idea, especially for real spectrum, the new topic on Hermitizable matrix is presented, including criteria and typical applications. This leads to the new framework, new spectral theory, and new algorithm of quantum mechanics (QM). The file in presentation is in English, but the talk is in Chinese.

• Zengqi Wang (Shanghai Jiao Tong University) (王增其, 上海交通大學)

1. Title: Modeling of reconstruction problems in computational spectrometer

2. Abstract: Optical spectrometers are the central instruments for exploring the interaction between light and matter. Although traditional spectrometers have simple measurement steps, they require complex wavelength multiplexing optics. The computational spectrometer is a portable spectrometer that can reconstruct the incident light spectrum based on the system’s spectral information and response photocurrents. The key to developing computational spectrometers is to establish and solve the spectral reconstruction model of incident light. In this talk, we discuss the different reconstruction models, such as such as TSVD, ridge regression, non-negative ridge regression, LASSO regression, L2–Lq minimization and L2−L1–LTV minimization models. Experiments show that the reconstructed model can effectively predict the information of incident light at a non-sampling wavelength.

• Qi Ye (South China Normal University) (葉齊, 華南師範大學)

1. Title: Machine Learning in Banach Spaces: A Black-box or White-box Method?

2. Abstract: In this talk, we present a new way to study the theory of regularized learning for generalized data in Banach spaces including representer theorems and convergence theorems. Specially, we combine the data-driven and model-driven methods to study the new algorithms and theorems of the regularized learning. Usually the data-driven and model-driven methods are used to analyze the black-box and white-box models, respectively. With the same thought of the Tai Chi diagram, we use the discrete information of the black-box and white-box local models to construct the global approximate solutions by the algorithms of the regularized learning. Our original ideas are inspired by the eastern philosophy such as the golden mean. The work of the regularized learning here provides another road to investigate the algorithms of machine learning including

• the interpretability in approximation theory,

• the nonconvexity and nonsmoothness in optimization theory,

• the generalization and overfitting in probability theory.

Moreover, based on the theory of the regularized learning, we will construct the hybrid algorithms combining support vector machines, artificial neural networks, and decision trees for our current research projects of the big data analytics in education and medicine.

2. 2022/05/08

• Gang Wu (China University of Mining and Technology)

1. Title: Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification

2. Abstract: Kernel methods are known to be effective to analyze complex objects by implicitly embedding them into some feature space. The approximate class-specific kernel spectral regression (ACS-KSR) method is a power tool for face verification. This method consists of two steps: an eigen-analysis step and a kernel regression step, however, it may suffer from heavily computational overhead in practice, especially for large-sample data sets. In this paper, we propose two randomized algorithms based on the ACS-KSR method. The main contribution of our work is as follows. First, we consider how to efficiently solve the ratio-trace problem and the trace-ratio problem involved in this method. Second, it is well known that kernel matrix is approximately low-rank, however, to the best of our knowledge, there are few theoretical results that can provide simple and feasible strategies to determine the numerical rank of a kernel matrix without forming it explicitly.

To fill-in this gap, we focus on the commonly used Gaussian kernel and provide a practical strategy for determining numerical rank of the kernel matrix. Third, based on numerically low-rank property of the kernel matrix, we propose a modified Nystr\"{o}m method with fixed-rank for the kernel regression step, and establish a probabilistic error bound on the approximation. Fourth, although the proposed Nystr\"{o}m method can reduce the computational cost of the original method, it is required to form and store the reduced kernel matrix explicitly. This is unfavorable to extremely large-sample data sets. To settle this problem, we propose a randomized block Kaczmarz method for kernel regression problem with multiple right-hand sides, in which there is no need to compute and store the reduced kernel matrix explicitly. The convergence of this method is established. Comprehensive numerical experiments on real-world data sets are performed to show the effectiveness of our theoretical results and the efficiency of the proposed methods.

• Meng Chen (Nanchang University)

1. Title: Kernel-based meshless methods for solving PDEs on surfaces

2. Abstract: We develop a new lineup of kernel-based meshless methods for surface partial differential equations by embedding, extrinsic projection and intrinsic formulations respectively. They enjoy the flexibility for yielding global and local numerical approaches, and are very natural to deal with surfaces defined by both parametric equations and point clouds. Their applications to complex physical models on surfaces include pattern formation by nonlinear reaction-diffusion equations, coupled bulk-surface problems, moving surfaces by heat transport equations, and etc.

• Ke Wei (Fudan University)

1. Title: Structured low rank matrix reconstruction: theory, methodology and applications

2. Abstract: Structured low rank matrix is an important model in signal processing and data analysis. In this talk we focus on two particular applications in signal processing: Spectrally sparse signal recovery and blind super-resolution of point sources. As can be seen, these two problems can be formulated as structured low rank matrix reconstruction problems. Based on this formulation, both convex and nonconvex methods can be developed for them. Moreover, theoretical recovery guarantees can be established for the reconstruction methods, showing that nearly optimal number of measurements are sufficient for successful reconstruction. Joint work with Jian-Feng Cai, Tiaming Wang (on spectrally sparse signal recovery), Jinchi Chen, Sihan Mao, and Weiguo Gao (on blind super-resolution of point sources).

3. 2022/05/28

• Bing Zheng (Lanzhou University) (鄭兵, 蘭州大學)

1. Title: A new self-scaling G-transformation for weighted least square problems

2. Abstract: The G-transformation is an efficient method for solving the weighted least squares problems. However, the underflows and overflows were not considered in the original G-transformation. In order to keep its stability, some specified scaling strategies has been proposed for guarding against the underflows. Note that these specific strategies are not easy to be implemented in actual operations, in this talk we present a self-scaling G-transformation (SSGT) which not only avoids these specified scaling strategies, but maintain the stability of operations. Complexity analysis of our self-scaling G-transformation shows that its cost of computation is less than that of the G-transformation, which implies the high efficiency of our proposed SSGT. The stability of the SSGT was theoretically confirmed by a detailed error analysis. Some numerical experiments are performed to illustrate the effects of the self-scaling strategy.

• Jinzhi Huang (Soochow University) (黃金枝 , 蘇州大學)

1. Title: A cross-product free Jacobi-Davidson type method for computing a partial generalized singular value decomposition of a large matrix pair

2. Abstract: In this talk, a Cross-Product Free (CPF) Jacobi–Davidson (JD) type method is proposed to compute a partial generalized singular value decomposition (GSVD) of a large regular matrix pair (A, B). It implicitly solves the mathematically equivalent generalized eigenvalue problem of (ATA,BTB) but does not explicitly form the cross-product matrices and thus avoids the possible accuracy loss of the computed generalized singular values and generalized singular vectors. The method is an inner-outer iteration method, where the expansion of the right searching subspace forms the inner iterations that approximately solve the correction equations involved and the outer iterations extract approximate GSVD components with respect to the subspaces. Some convergence results are established for the inner and outer iterations, based on some of which practical stopping criteria are designed for the inner iterations. A thick-restart CPF-JDGSVD algorithm with deflation and purgation is developed to compute several GSVD components. Numerical experiments illustrate the efficiency of the algorithm.

• Chun-Hua Zhang (Nanchang Hangkong University) (張春華, 南昌航空大學)

1. Title: A positivity-preserving IMEX scheme for evolutionary stable distribution model

2. Abstract: In this work, we study the numerical solutions for the integro-differential equation that describes the evolution of a population structured with respect to a continuous trait. A new implicit-explicit scheme is proposed to discretize the evolutionary stable distribution model with long time behavior, which can keep the positivity of the numerical solution at each time step. To discretize the time variable, our idea is to keep positive terms in both side of the equation. Theoretically, we prove that the proposed scheme is unconditionally positivity-preserving and satisfies the entropy dissipation inequality under some conditions on coefficients. Numerical experiments are carried out to demonstrate the numerical accuracy and the effectiveness of the proposed scheme.

4. 2022/06/25

• Bo Dong (Dalian University of Technology) (董波, 大連理工大學)

1. Title: Structured Multiparameter Eigenvalue Problems-Algorithms and Applications

2. Abstract: Structured linear/nonlinear multiparameter eigenvalue problems arise in many applications, such as the multiparameter Sturm-Liouville theory, the analysis of the asymptotic stability of the delay differential equation, the reconstruction of the physical mass-spring system and the analysis of the semistructured aeroelastic flutter problems. In this talk, I will introduce the background of the multiparameter eigenvalue problems, and then introduce two classes of numerical methods: those that deal with the problems directly and those that compute the eigenvalues of the transformed simultaneous eigenvalue problems. Finally, some theoretical analysis and numerical experiments are presented to illustrate the advantages and disadvantages of these two classes of methods.

• WeiWei Xu (Nanjing University of Information Technology) (徐瑋瑋, 南京信息工程大學)

1. Title: Randomized algorithms with low-rank matrix approximations for fast computing comparative analysis of a class of genome-scale expression data sets

2. Abstract: In this talk, randomized algorithm with low-rank matrix approximations is constructed for fast computing angular distances, generalized fractions of eigen-expression and generalized normalized Shannon entropy for comparative analysis of genome-scale expression data sets. Both for synthetic data sets and practical genome-scale expression data sets numerical experiments are reported to illustrate fast performance of the proposed method compared with the existing state-of-the-art methods.

• Ching-Sung Liu (National University of Kaohsiung)

1. Title: Newton-Noda iteration for nonlinear eigenvalue problems

2. Abstract: In this talk, we will introduce nonlinear eigenvalue problems, including tensor eigenvalue problems and nonlinear Schrödinger equations. We present a Newton-Noda iteration (NNI) to find positive eigenvectors of nonlinear problems. A great advantage of this method is that it converges quadratically and maintains positivity, i.e., the vector approximating the Perron vector (or ground state vector) is strictly positive in each iteration.

1. 2022/10/29

• Hengbin An (Institute of Applied Physics and Computational Mathematics: Beijing) (安恒斌, 北京應用物理與計算數學研究所)

1. Title: A Physics-Based Iterative Initial Value Construction Method for Solving Drift-Diffusion Equations

2. Abstract: The drift-diffusion equation needs to be solved in numerical simulation applications of semiconductor devices. The equations are a coupled nonlinear system of equations including a potential equation, an electron concentration equation, and a hole concentration equation. Therefore, after discretizing the drift-diffusion equation, it is necessary to solve the large-scale nonlinear algebraic equations obtained by discretization. Due to the strong nonlinear characteristics of the drift-diffusion equation, when the Newton iterative method or the Gummel iterative method is used to solve the problem, the nonlinear iterative process converges slowly or even does not converge. In order to improve the nonlinear iterative convergence, this report introduces a class of nonlinear iterative initial values constructed based on the application characteristics of the drift-diffusion equation. An estimate of the error between the constructed initial value and the solution of the equation is given. Numerical results show that the number of nonlinear iterations can be significantly reduced by using the newly proposed initial value compared to the initial value of iteration commonly used in practical applications. In some cases, the nonlinear iteration is difficult to converge when using the commonly used initial value of the iteration, but the nonlinear iteration can converge with the new initial value of the iteration.

• Qingqing Zheng (China University of Petroleum) (鄭青青, 中國石油大學)

1. Title: An analysis of the Rayleigh-Ritz and refined Rayleigh-Ritz Methods for nonlinear eigenvalue problem

2. Abstract: In this talk, we analyze the Rayleigh-Ritz method and the refined Rayleigh-Ritz method for computing an approximation of a simple eigenpair (λ∗, x∗) of a given nonlinear eigenvalue problem. For a given subspace W that contains a sufficiently accurate approximation to x∗, we establish convergence results on the Ritz value, the Ritz vector and the refined Ritz vector as the deviation ε of x∗ from W approaches zero. We also derive lower and upper bounds for the error of the refined Ritz vector and the Ritz vector as well as for that of the corresponding residual norms. These results extend the convergence results of these two methods for the linear eigenvalue problem to the nonlinear case. We construct examples to illustrate some of the results.

• Xiaoshan Chen (South China Normal University) (陳小山, 華南師範大學)

1. Title: QR algorithm with two-sided Rayleigh quotient shifts

2. Abstract: We introduce the two-sided Rayleigh quotient shift for the QR algorithm for non-Hermitian matrices. For the singly shifted case, the two-sided Rayleigh quotient iteration is incorporated in the QR iteration in an economic manner. A modified version of the method is proposed, where the two-sided Rayleigh quotient is computed directly from current upper Hessenberg matrix. Based on the observation that the Francis double-shift QR iteration is related to a 2D Grassmann-Rayleigh quotient iteration, we propose the doubly shifted QR algorithm with the two-sided 2D Grassmann-Rayleigh quotient double-shift. A modified version of the method is also proposed. For semi-simple eigenvalues, we claim that the QR algorithm with either the two-sided Rayleigh quotient shift or the 2D Grassmann-Rayleigh quotient double-shift has a cubic local convergence rate. Numerical examples are presented to support the claim. The proposed algorithms may be used for computing the Schur form of submatrices needed in the multishift QR algorithm with aggressive early deflation.

2. 2022/11/26

• Bingjie Li (National University of Singapore, 李冰杰)

1. Title: Exterior Point Method for Completely Positive Factorization

2. Abstract: Completely positive factorization (CPF) is an open problem with applications in many fields. This talk introduces a novel method for CPF, named as Exterior Point Method (EPM). It solves a simple optimization problem, without any restrictions such as nonnegativity or orthogonality that are commonly used in literature, though the convergent point is asked to obey these two restrictions eventually. Because of free constraint, this optimization problem can be solved efficiently via a modified nonlinear conjugate gradient method. Theoretical analysis is given to support this approach. A restarting technique is also developed to jump out local optimums in difficult cases. Via re-estimating the global optimum from a local optimum and using the estimation as a new starting point, the EPM performs much better than other algorithms, not only in the efficiency of computational cost or accuracy but also in the ability to address the CPF in some hard cases.

• Xin Lu (China University of Petroleum, 盧欣)

1. Title: A structure-preserving algorithm for palindromic eigenvalue problems

2. Abstract: Palindromic eigenvalue problems (PEP) are widely used in many fields, such as high-speed railway vibration problems. A new structure-preserving algorithm has been studied for palindromic polynomial eigenvalue problems. It has been shown that PEP can be linearized into a symplectic pencil, which preserves the symmetry structure of eigenvalues of the original PEP, and only orthogonal transformations are used whenever possible. The efficiency of the algorithm has also been demonstrated by some examples.

• Chun-Yueh Chiang (National Formosa University)

1. Title: Recent advances in the conjugate discrete-time algebraic Riccati equation

2. Abstract: In this talk, we consider a class of conjugate discrete-time Riccati equations (CDARE), arising originally from the linear quadratic regulation problem for discrete-time antilinear systems. Our contribution is twofold:

First, under some mild assumptions and the framework of the fixed-point iteration, a constructive proof is given for the existence of the maximal solution to the conjugate discrete-time Riccati equation, in which the control weighting matrix is nonsingular and its constant term is Hermitian. Moreover, starting with a suitable initial matrix, we also show that the nonincreasing sequence generated by the fixed-point iteration converges at least linearly to the maximal solution of the Riccati equation.

Second, CDARE can be transformed into the discrete-time algebraic Riccati equation(DARE) via some computations and substitutions. An accelerated fixed-point iteration (AFPI) based on the semigroup property is developed for computing four extremal solutions of the DARE. In addition, we prove that the convergence of the AFPI is at least R-suplinear with order $r>1$ under some mild assumptions.

An example is given to demonstrate the correctness of our main theorem and provide considerable insights into the study of another meaningful solutions.

3. 2022/12/24

• Yue Qiu (ShanghaiTech University) (邱越, 上海科技大學)

1. Title: Low-rank Methods for Bayesian Inverse Problems

2. Abstract: In this talk, I will introduce our recent work on low-rank methods for Bayesian inverse problems. For linear problems with Gaussian noise and Gaussian prior, the posterior is also Gaussian and characterized by the posterior mean and covariance. We propose a low rank Arnoldi method to approximate the large dense posterior covariance matrix by making use of tensor computations. For nonlinear systems, the posterior is not Gaussian anymore, however, can often be approximated by a Gaussian distribution using the ensemble Kalman filter (EnKF) or the extended Kalman filter (ExKF). We propose a randomized low-rank method to reduce the computational complexity of the EnKF. We use numerical experiments to show the efficiency of our low-rank methods.

• Liping Zhang (Zhejiang University of Technology) (張理評, 浙江工業大學)

1. Title: Randomized Algorithms for Discrete Ill-Posed Problems

2. Abstract: We propose randomized GSVD algorithms and a randomized core reduction for the ill-posed problem with the tolerance as a regularization parameter. In theory and numerical experiments, we show that the randomized algorithms are competitive with the truncated GSVD/TLS in accuracy and more efficient in time and storage. For the large-scale problem, the coefficient matrix does not need to be explicit.

• Hongjia Chen (Nanchang University) (諶鴻佳, 南昌大學)

1. Title: Solving the polynomial eigenvalue problem expressed in non-monomial basis by the scaled CORK linearization

2. Abstract: One of the most successful methods for solving a polynomial (PEP) or rational eigenvalue problem (REP) is to recast it, by linearization, as an equivalent but larger generalized eigenvalue problem which can be solved by standard eigensolvers. In this work, we investigate the backward errors of the computed eigenpairs incurred by the application of the well-received compact rational Krylov (CORK) linearization. Our treatment is unified for the PEPs or REPs expressed in various commonly used bases, including Taylor, Newton, Lagrange, orthogonal, and rational basis functions. We construct one-sided factorizations that relate the eigenpairs of the CORK linearization and those of the PEPs or REPs. With these factorizations, we establish upper bounds for the backward error of an approximate eigenpair of the PEPs or REPs relative to the backward error of the corresponding eigenpair of the CORK linearization. These bounds suggest a scaling strategy to improve the accuracy of the computed eigenpairs. We show, by numerical experiments, that the actual backward errors can be successfully reduced by scaling and the errors, before and after scaling, are both well predicted by the bounds.

4. 2023/01/09, Tencent Meeting, Meeting ID: 759-597-111, Password: 0109

• Jianlin Xia (夏建林, Purdue University)

1. Title: Accurate analytical and randomized low-rank approximations of kernel matrices

2. Abstract: In this talk, we discuss some methods and analysis for fast and accurate low-rank approximations of kernel matrices. We will focus on two types of methods: analytical ones and randomized ones, both have nearly linear complexity and can reach high accuracy for various kernel matrices. Analytical methods may be used to explicitly write a kernel-independent approximate basis matrix without the need of algebraic compression. We will particularly show an intuitive way to understand one type of analytical methods called proxy point methods. Proxy point methods have been widely used in PDE and integral equation solutions but were not well known in the field of matrix computations due to the lack of algebraic error/rank analysis. We use contour integration strategies to present rigorous algebraic error bounds and further provide optimal parameter choices. We will also present a new randomized low-rank approximation method that can reach nearly SVD-quality for some kernel matrices. The method is based on the Nystrom method that has been extensively used in data analysis. The classical Nystrom method is not suitable for high-accuracy approximations due to the lack of accuracy guaranty unless very high sample sizes are used. Here, we show a new idea that uses sample sizes comparable to the target numerical ranks to reach high accuracy.

• Juan Zhang (Xiangtan University) (張娟, 湘潭大学)

1. Title: Calculation Method of Lattice Grain Boundary at Non-coincident Location in FCC

2. Abstract: A grain boundary is an interface formed between grains with the same structure but different orientations. It plays a crucial role in the performance of polycrystalline materials. After decades of research, people have a good understanding of periodic grain boundaries (i.e., periodic interfaces). However, most grain boundaries are non-periodic, or quasi-periodic. It has always been a challenge to study non-periodic grain boundaries. In this report, we establish a unified computational framework for studying periodic and non-periodic grain boundaries based on the projection method, and use the Landau-Brazovskii model to study the grain boundary structure of FCC symmetry tilting. We have discovered a non-periodic grain boundary with atoms arranged in a generalized Fabonacci sequence.

• Luo Luo (羅珞, Fudan University)

1. Title: Streaming Algorithms for Matrix Approximation

2. Abstract: In this talk, we introduce the matrix sketching algorithms in the row-updates model. For symmetric positive definite matrix, we introduce the idea of regularized matrix approximation and its application in streaming model, which leads to the more accurate and more well-conditioned estimation than the results of classical low-rank based algorithms. For the general streaming matrix multiplication, we introduce the sharper error bound of co-occurring directions and its extension for sparse inputs. We also discuss time and space optimality of these algorithms.

5. A