Huiyuan Li

Huiyuan Li, Jiachang Sun, Yuan Xu

Several problems of trigonometric approximation on a hexagon and a triangle are studied using the discrete Fourier transform and orthogonal polynomials of two variables. A discrete Fourier analysis on the regular hexagon is developed in detail, from which the analysis on the triangle is deduced. The results include cubature formulas and interpolation on these domains. In particular, a trigonometric Lagrange interpolation on a triangle is shown to satisfy an explicit compact formula, which is equivalent to the polynomial interpolation on a planer region bounded by Steiner's hypocycloid. The Lebesgue constant of the interpolation is shown to be in the order of $(\log n)^2$. Furthermore, a Gauss cubature is established on the hypocycloid.

Wenjie Liu, Li-Lian Wang, Huiyuan Li

In this paper, we introduce a new theoretical framework built upon fractional Sobolev-type spaces involving Riemann-Liouville (RL) fractional integrals/derivatives, which is naturally arisen from exact representations of Chebyshev expansion coefficients, for optimal error estimates of Chebyshev approximations to functions with limited regularity. The essential pieces of the puzzle for the error analysis include (i) fractional integration by parts (under the weakest possible conditions), and (ii) generalised Gegenbauer functions of fractional degree (GGF-Fs): a new family of special functions with notable fractional calculus properties. Under this framework, we are able to estimate the optimal decay rate of Chebyshev expansion coefficients for a large class of functions with interior and endpoint singularities, which are deemed suboptimal or complicated to characterize in existing literature. We can then derive optimal error estimates for spectral expansions and the related Chebyshev interpolation and quadrature measured in various norms, and also improve the available results in usual Sobolev spaces of integer regularity exponentials in several senses. As a by-product, this study results in some analytically perspicuous formulas particularly on GGF-Fs, which are potentially useful in spectral algorithms. The idea and analysis techniques can be extended to general Jacobi spectral approximations.

Jing Zhang, Huiyuan Li, Li-Lian Wang et al.

In this paper, we introduce the prolate spheroidal wave functions (PSWFs) of real order $α>-1$ on the unit ball in arbitrary dimension, termed as ball PSWFs. They are eigenfunctions of both a weighted concentration integral operator, and a Sturm-Liouville differential operator. Different from existing works on multi-dimensional PSWFs, the ball PSWFs are defined as a generalisation of orthogonal {\em ball polynomials} in primitive variables with a tuning parameter $c>0$, through a "perturbation" of the Sturm-Liouville equation of the ball polynomials. From this perspective, we can explore some interesting intrinsic connections between the ball PSWFs and the finite Fourier and Hankel transforms. We provide an efficient and accurate algorithm for computing the ball PSWFs and the associated eigenvalues, and present various numerical results to illustrate the efficiency of the method. Under this uniform framework, we can recover the existing PSWFs by suitable variable substitutions.

Michael Daniel Samson, Huiyuan Li, Li-Lian Wang

This paper serves as our first effort to develop a new triangular spectral element method (TSEM) on unstructured meshes, using the rectangle-triangle mapping proposed in the conference note [21]. Here, we provide some new insights into the originality and distinctive features of the mapping, and show that this transform only induces a logarithmic singularity, which allows us to devise a fast, stable and accurate numerical algorithm for its removal. Consequently, any triangular element can be treated as efficiently as a quadrilateral element, which affords a great flexibility in handling complex computational domains. Benefited from the fact that the image of the mapping includes the polynomial space as a subset, we are able to obtain optimal $L^2$- and $H^1$-estimates of approximation by the proposed basis functions on triangle. The implementation details and some numerical examples are provided to validate the efficiency and accuracy of the proposed method. All these will pave the way for developing an unstructured TSEM based on, e.g., the hybridizable discontinuous Galerkin formulation.

Huiyuan Li, Yuan Xu

A discrete Fourier analysis on the dodecahedron is studied, from which results on a tetrahedron is deduced by invariance. The results include Fourier analysis in trigonometric functions, interpolation and cubature formulas on these domains. In particular, a trigonometric Lagrange interpolation on the tetrahedron is shown to satisfy an explicit compact formula and the Lebesgue constant of the interpolation is shown to be in the order of $(\log n)^3$.

Huiyuan Li, Zhimin Zhang

In this article, we study numerical approximation of eigenvalue problems of the Schrödinger operator $\displaystyle -Δu + \frac{c^2}{|x|^2}u$. There are three stages in our investigation: We start from a ball of any dimension, in which case the exact solution in the radial direction can be expressed by Bessel functions of fractional degrees. This knowledge helps us to design two novel spectral methods by modifying the polynomial basis to fit the singularities of the eigenfunctions. At the second stage, we move to circular sectors in the two dimensional setting. Again the radial direction can be expressed by Bessel functions of fractional degrees. Only in the tangential direction some modifications are needed from stage one. At the final stage, we extend the idea to arbitrary polygonal domains. We propose a mortar spectral element approach: a polygonal domain is decomposed into several sub-domains with each singular corner including the origin covered by a circular sector, in which origin and corner singularities are handled similarly as in the former stages, and the remaining domains are either a standard quadrilateral/triangle or a quadrilateral/triangle with a circular edge, in which the traditional polynomial based spectral method is applied. All sub-domains are linked by mortar elements (note that we may have hanging nodes). In all three stages, exponential convergence rates are achieved. Numerical experiments indicate that our new methods are superior to standard polynomial based spectral (or spectral element) methods and $hp$-adaptive methods. Our study offers a new and effective way to handle eigenvalue problems of the Schrödinger operator including the Laplacian operator on polygonal domains with reentrant corners.

Huiyuan Li, Jiachang Sun, Yuan Xu

The discrete Fourier analysis on the $30^{\degree}$-$60^{\degree}$-$90^{\degree}$ triangle is deduced from the corresponding results on the regular hexagon by considering functions invariant under the group $G_2$, which leads to the definition of four families generalized Chebyshev polynomials. The study of these polynomials leads to a Sturm-Liouville eigenvalue problem that contains two parameters, whose solutions are analogues of the Jacobi polynomials. Under a concept of $m$-degree and by introducing a new ordering among monomials, these polynomials are shown to share properties of the ordinary orthogonal polynomials. In particular, their common zeros generate cubature rules of Gauss type.

Huiyuan Li, Yuan Xu

A discrete Fourier analysis on the fundamental domain $Ω_d$ of the $d$-dimensional lattice of type $A_d$ is studied, where $Ω_2$ is the regular hexagon and $Ω_3$ is the rhombic dodecahedron, and analogous results on $d$-dimensional simplex are derived by considering invariant and anti-invariant elements. Our main results include Fourier analysis in trigonometric functions, interpolation and cubature formulas on these domains. In particular, a trigonometric Lagrange interpolation on the simplex is shown to satisfy an explicit compact formula and the Lebesgue constant of the interpolation is shown to be in the order of $(\log n)^d$. The basic trigonometric functions on the simplex can be identified with Chebyshev polynomials in several variables already appeared in literature. We study common zeros of these polynomials and show that they are nodes for a family of Gaussian cubature formulas, which provides only the second known example of such formulas.

Huiyuan Li, Jiachang Sun, Yuan Xu

Several cubature formulas on the cubic domains are derived using the discrete Fourier analysis associated with lattice tiling, as developed in \cite{LSX}. The main results consist of a new derivation of the Gaussian type cubature for the product Chebyshev weight functions and associated interpolation polynomials on $[-1,1]^2$, as well as new results on $[-1,1]^3$. In particular, compact formulas for the fundamental interpolation polynomials are derived, based on $n^3/4 +\CO(n^2)$ nodes of a cubature formula on $[-1,1]^3$.

Lizhen Chen, Zhiping Mao, Huiyuan Li

An efficient Jacobi-Galerkin spectral method for calculating eigenvalues of Riesz fractional partial differential equations with homogeneous Dirichlet boundary values is proposed in this paper. In order to retain the symmetry and positive definiteness of the discrete linear system, we introduce some properly defined Sobolev spaces and approximate the eigenvalue problem in a standard Galerkin weak formulation instead of the Petrov-Galerkin one as in literature. Poincaré and inverse inequalities are proved for the proposed Galerkin formulation which finally help us establishing a sharp estimate on the algebraic system's condition number. Rigorous error estimates of the eigenvalues and eigenvectors are then readily obtained by using Babuška and Osborn's approximation theory on self-adjoint and positive-definite eigenvalue problems. Numerical results are presented to demonstrate the accuracy and efficiency, and to validate the asymptotically exponential oder of convergence. Moreover, the Weyl-type asymptotic law $ λ_n=\mathcal{O}(n^{2α})$ for the $n$-th eigenvalue $λ_n$ of the Riesz fractional differential operator of order $2α$, and the condition number $N^{4α}$ of its algebraic system with respect to the polynomial degree $N$ are observed.

Jing An, Huiyuan Li, Zhimin Zhang

In this paper we propose and analyze spectral-Galerkin methods for the Stokes eigenvalue problem based on the stream function formulation in polar geometries. We first analyze the stream function} formulated fourth-order equation under the polar coordinates, then we derive the pole condition and reduce the problem on a circular disk to a sequence of equivalent one-dimensional eigenvalue problems that can be solved in parallel. The novelty of our approach lies in the construction} of suitably weighted Sobolev spaces according to the pole conditions, based on which, the optimal error estimate for approximated eigenvalue of each one dimensional problem can be obtained. Further, we extend our method to the non-separable Stokes eigenvalue problem in an elliptic domain and establish the optimal error bounds. Finally, we provide some numerical experiments to validate our theoretical results and algorithms.

Ziwei Li, Tao Yuan, Shuzi Niu et al.

Sparse matrix reordering can significantly reduce the fill-in during matrix factorization, thereby decreasing the computational and storage requirements in sparse matrix computations. Finding a minimal fill-in ordering is known to be an NP-hard problem. Moreover, there is a paradox: matrix reordering is applied before matrix factorization, but fill-ins that matrix reordering methods aim at are generated from matrix factorization. To bridge the gap between reordering and factorization, we propose a deep learning framework to minimize a fill-in surrogate function based on spectral embedding. First, we employ a multi-grid-like GNN architecture to learn to approximate the smallest eigenvectors of its graph Laplacian matrix, i.e. spectral embedding, and capture the global structural information of the matrix. Then, another multi-grid-like GNN architecture is used to minimize the potential space where fill-in can occur based on the rank distribution. Experimental results indicate that our approach achieves competitive performance compared with traditional graph-theoretic algorithms and deep learning methods.

Ziwei Li, Tao Yuan, Fangfang Liu et al.

Rearranging the rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins, i.e., new nonzeros introduced during matrix factorization, decreasing memory usage and runtime. However, finding an ordering that minimizes fill-ins is NP-complete. Existing approaches, including graph-theoretic and deep learning methods, rely on surrogate objectives without theoretical guarantees. The Fill-Path Theorem reveals a direct and intrinsic relationship between fill-in generation and the sparse structure of the matrix as path triplet inequalities. Here we first employ a multigrid graph network to capture structural information for each vertex. We then derive a triplet sampling strategy based on inequalities. Finally, we introduce an end-max chain loss function to reduce the number of triplets whose predicted scores satisfy these inequalities. Experimental evaluations on the publicly available SuiteSparse matrix collection demonstrate the superiority of the proposed method in terms of both fill-in reduction and speedup in LU factorization time.

Ziwei Li, Shuzi Niu, Huiyuan Li et al.

Matrix reordering in large sparse solvers seeks a permutation that minimizes factorization fill-in to reduce memory and computation. Because the minimum fill-in ordering problem is NP-complete and fill-in is implicit in the sparsity pattern, graph-theoretic heuristics are used. Existing reinforcement learning methods either ignore sparsity patterns--missing the global fill-in--or lack local exact fill-in feedback. We propose a graph policy optimization method, modeling fill-ins from global and local views: both the policy and value networks use a multi-hop graph neural backbone to embed global fill-in; the policy further interacts with symbolic factorization over graphs to extract local, step-level fill-ins, and the resulting feedback is aligned with the value network via an adaptive saturation function to improve convergence. On the SuiteSparse Matrix Collection, our method achieves mean reductions of 29.3 in fill-ins and 31.3 in peak memory usage over state-of-the-art baselines.

Ziwei Li, Shuzi Niu, Tao Yuan et al.

Fill-ins are new nonzero elements in the summation of the upper and lower triangular factors generated during LU factorization. For large sparse matrices, they will increase the memory usage and computational time, and be reduced through proper row or column arrangement, namely matrix reordering. Finding a row or column permutation with the minimal fill-ins is NP-hard, and surrogate objectives are designed to derive fill-in reduction permutations or learn a reordering function. However, there is no theoretical guarantee between the golden criterion and these surrogate objectives. Here we propose to learn a reordering network by minimizing \(l_1\) norm of triangular factors of the reordered matrix to approximate the exact number of fill-ins. The reordering network utilizes a graph encoder to predict row or column node scores. For inference, it is easy and fast to derive the permutation from sorting algorithms for matrices. For gradient based optimization, there is a large gap between the predicted node scores and resultant triangular factors in the optimization objective. To bridge the gap, we first design two reparameterization techniques to obtain the permutation matrix from node scores. The matrix is reordered by multiplying the permutation matrix. Then we introduce the factorization process into the objective function to arrive at target triangular factors. The overall objective function is optimized with the alternating direction method of multipliers and proximal gradient descent. Experimental results on benchmark sparse matrix collection SuiteSparse show the fill-in number and LU factorization time reduction of our proposed method is 20% and 17.8% compared with state-of-the-art baselines.

Fu-jun Liu, Zhong-qing Wang, Huiyuan Li

A fully diagonalized spectral method using generalized Laguerre functions is proposed and analyzed for solving elliptic equations on the half line. We first define the generalized Laguerre functions which are complete and mutually orthogonal with respect to an equivalent Sobolev inner product. Then the Fourier-like Sobolev orthogonal basis functions are constructed for the diagonalized Laguerre spectral method of elliptic equations. Besides, a unified orthogonal Laguerre projection is established for various elliptic equations. On the basis of this orthogonal Laguerre projection, we obtain optimal error estimates of the fully diagonalized Laguerre spectral method for both Dirichlet and Robin boundary value problems. Finally, numerical experiments, which are in agreement with the theoretical analysis, demonstrate the effectiveness and the spectral accuracy of our diagonalized method.

Huiyuan Li, Jiachang Sun, Yuan Xu

A discrete Fourier analysis associated with translation lattices is developed recently by the authors. It permits two lattices, one determining the integral domain and the other determining the family of exponential functions. Possible choices of lattices are discussed in the case of lattices that tile $\RR^2$ and several new results on cubature and interpolation by trigonometric, as well as algebraic, polynomials are obtained.