We establish a lower bound for the complexity of multiplying two skew polynomials. The lower bound coincides with the upper bound conjectured by Caruso and Borgne in 2017, up to a log factor. We present algorithms for three special cases, indicating that the aforementioned lower bound is quasi-optimal. In fact, our lower bound is quasi-optimal in the sense of bilinear complexity. In addition, we discuss the average bilinear complexity of simultaneous multiplication of skew polynomials and the complexity of skew polynomial multiplication in the case of towers of extensions.
This paper studies the convergence of a spatial semidiscretization of a three-dimensional stochastic Allen-Cahn equation with multiplicative noise. For non-smooth initial values, the regularity of the mild solution is investigated, and an error estimate is derived with the spatial $ L^2 $-norm. For smooth initial values, two error estimates with the general spatial $ L^q $-norms are established.
A simplified kinetic description of rapid granular media leads to a nonlocal Vlasov-type equation with a convolution integral operator that is of the same form as the continuity equations for aggregation-diffusion macroscopic dynamics. While the singular behavior of these nonlinear continuity equations is well studied in the literature, the extension to the corresponding granular kinetic equation is highly nontrivial. The main question is whether the singularity formed in velocity direction will be enhanced or mitigated by the shear in phase space due to free transport. We present a preliminary study through a meticulous numerical investigation and heuristic arguments. We have numerically developed a structure-preserving method with adaptive mesh refinement that can effectively capture potential blow-up behavior in the solution for granular kinetic equations. We have analytically constructed a finite-time blow-up infinite mass solution and discussed how this can provide insights into the finite mass scenario.
We consider the fundamental task of optimising a real-valued function defined in a potentially high-dimensional Euclidean space, such as the loss function in many machine-learning tasks or the logarithm of the probability distribution in statistical inference. We use Riemannian geometry notions to redefine the optimisation problem of a function on the Euclidean space to a Riemannian manifold with a warped metric, and then find the function's optimum along this manifold. The warped metric chosen for the search domain induces a computational friendly metric-tensor for which optimal search directions associated with geodesic curves on the manifold becomes easier to compute. Performing optimization along geodesics is known to be generally infeasible, yet we show that in this specific manifold we can analytically derive Taylor approximations up to third-order. In general these approximations to the geodesic curve will not lie on the manifold, however we construct suitable retraction maps to pull them back onto the manifold. Therefore, we can efficiently optimize along the approximate geodesic curves. We cover the related theory, describe a practical optimization algorithm and empirically evaluate it on a collection of challenging optimisation benchmarks. Our proposed algorithm, using 3rd-order approximation of geodesics, tends to outperform standard Euclidean gradient-based counterparts in term of number of iterations until convergence.
Acoustic wave equation is a partial differential equation (PDE) which describes propagation of acoustic waves through a material. In general, the solution to this PDE is nonunique. Therefore, initial conditions in the form of Cauchy conditions are imposed for obtaining a unique solution. Theoretically, solving the wave equation is equivalent to representing the wavefield in terms of a radiation source which possesses finite energy over space and time. In practice, the source may be represented in terms of pressure, normal derivative of pressure or normal velocity over a surface. The pressure wavefield is then calculated by solving an associated boundary value problem via imposing conditions on the boundary of a chosen solution space. From an analytic point of view, this manuscript aims to review typical approaches for obtaining unique solution to the acoustic wave equation in terms of either a volumetric radiation source $s$, or a singlet surface source in terms of normal derivative of pressure $(\partial/\partial \boldsymbol{n})p$ or its equivalent $\rho_0 u^{\boldsymbol{n}}$ with $\rho_0$ the ambient density, where $u^{\boldsymbol{n}} = \boldsymbol{u} \cdot \boldsymbol{n}$ is the normal velocity with $\boldsymbol{n}$ a unit vector outwardly normal to the surface. For some cases including a time-reversal propagation, the surface source is defined as a doublet source in terms of pressure $p$. A numerical approximation of the derived formulae will then be explained. The key step for numerically approximating the derived analytic formulae is inclusion of source, and will be studied carefully in this manuscript. It will be shown that compared to an analytical or ray-based solutions using Green's function, a numerical approximation of acoustic wave equation for a doublet source has a limitation regarding how to account for solid angles efficiently.
We propose a new Riemannian gradient descent method for computing spherical area-preserving mappings of topological spheres using a Riemannian retraction-based framework with theoretically guaranteed convergence. The objective function is based on the stretch energy functional, and the minimization is constrained on a power manifold of unit spheres embedded in 3-dimensional Euclidean space. Numerical experiments on several mesh models demonstrate the accuracy and stability of the proposed framework. Comparisons with two existing state-of-the-art methods for computing area-preserving mappings demonstrate that our algorithm is both competitive and more efficient. Finally, we present a concrete application to the problem of landmark-aligned surface registration of two brain models.
Symplectic integrators are widely implemented numerical integrators for Hamiltonian mechanics, which preserve the Hamiltonian structure (symplecticity) of the system. Although the symplectic integrator does not conserve the energy of the system, it is well known that there exists a conserving modified Hamiltonian, called the shadow Hamiltonian. For the Nambu mechanics, which is one of the generalized Hamiltonian mechanics, we can also construct structure-preserving integrators by the same procedure used to construct the symplectic integrators. In the structure-preserving integrator, however, the existence of shadow Hamiltonians is non-trivial. This is because the Nambu mechanics is driven by multiple Hamiltonians and it is non-trivial whether the time evolution by the integrator can be cast into the Nambu mechanical time evolution driven by multiple shadow Hamiltonians. In the present paper we construct structure-preserving integrators for a simple Nambu mechanical system, and derive the shadow Hamiltonians in two ways. This is the first attempt to derive shadow Hamiltonians of structure-preserving integrators for Nambu mechanics. We show that the fundamental identity, which corresponds to the Jacobi identity in Hamiltonian mechanics, plays an important role to calculate the shadow Hamiltonians using the Baker-Campbell-Hausdorff formula. It turns out that the resulting shadow Hamiltonians have indefinite forms depending on how the fundamental identities are used. This is not a technical artifact, because the exact shadow Hamiltonians obtained independently have the same indefiniteness.
Regression models that incorporate smooth functions of predictor variables to explain the relationships with a response variable have gained widespread usage and proved successful in various applications. By incorporating smooth functions of predictor variables, these models can capture complex relationships between the response and predictors while still allowing for interpretation of the results. In situations where the relationships between a response variable and predictors are explored, it is not uncommon to assume that these relationships adhere to certain shape constraints. Examples of such constraints include monotonicity and convexity. The scam package for R has become a popular package to carry out the full fitting of exponential family generalized additive modelling with shape restrictions on smooths. The paper aims to extend the existing framework of shape-constrained generalized additive models (SCAM) to accommodate smooth interactions of covariates, linear functionals of shape-constrained smooths and incorporation of residual autocorrelation. The methods described in this paper are implemented in the recent version of the package scam, available on the Comprehensive R Archive Network (CRAN).
In this article, we propose a fully-discrete scheme for the numerical solution of a nonlinear time-fractional biharmonic problem. This problem is first converted into an equivalent system by introducing a new variable. Then spatial and temporal discretizations are done by the weighted $b$-spline method and $L2$-$1_\sigma$ approximation, respectively. The weighted $b$-spline method uses weighted $b$-splines on a tensor product grid as basis functions for the finite element space and by construction, it is a mesh-free method. This method combines the computational benefits of $b$-splines and standard mesh-based elements. We derive $\alpha$-robust \emph{a priori} bound and convergence estimate in the $L^2(\Omega)$ norm for the proposed scheme. Finally, we carry out few numerical experiments to support our theoretical findings.
We establish an invariance principle for polynomial functions of $n$ independent high-dimensional random vectors, and also show that the obtained rates are nearly optimal. Both the dimension of the vectors and the degree of the polynomial are permitted to grow with $n$. Specifically, we obtain a finite sample upper bound for the error of approximation by a polynomial of Gaussians, measured in Kolmogorov distance, and extend it to functions that are approximately polynomial in a mean squared error sense. We give a corresponding lower bound that shows the invariance principle holds up to polynomial degree $o(\log n)$. The proof is constructive and adapts an asymmetrisation argument due to V. V. Senatov. As applications, we obtain a higher-order delta method with possibly non-Gaussian limits, and generalise a number of known results on high-dimensional and infinite-order U-statistics, and on fluctuations of subgraph counts.
We investigate a convective Brinkman--Forchheimer problem coupled with a heat transfer equation. The investigated model considers thermal diffusion and viscosity depending on the temperature. We prove the existence of a solution without restriction on the data and uniqueness when the solution is slightly smoother and the data is suitably restricted. We propose a finite element discretization scheme for the considered model and derive convergence results and a priori error estimates. Finally, we illustrate the theory with numerical examples.