We propose a CJ-FEAST GSVDsolver to compute a partial generalized singular value decomposition (GSVD) of a large matrix pair $(A,B)$ with the generalized singular values in a given interval. The solver is a highly nontrivial extension of the FEAST eigensolver for the (generalized) eigenvalue problem and CJ-FEAST SVDsolver for the SVD problem. For a partial GSVD problem, given three left and right searching subspaces, we propose a general projection method that works on $(A,B)$ {\em directly}, and computes approximations to the desired GSVD components. For the concerning GSVD problem, we exploit the Chebyshev--Jackson (CJ) series to construct an approximate spectral projector of the generalized eigenvalue problem of the matrix pair $(A^TA,B^TB)$ associated with the generalized singular values of interest, and use subspace iteration on it to generate a right subspace. Premultiplying it with $A$ and $B$ constructs two left subspaces. Applying the general projection method to the subspaces constructed leads to the CJ-FEAST GSVDsolver. We derive accuracy estimates for the approximate spectral projector and its eigenvalues, and establish a number of convergence results on the underlying subspaces and the approximate GSVD components obtained by the CJ-FEAST GSVDsolver. We propose general-purpose choice strategies for the series degree and subspace dimension. Numerical experiments illustrate the efficiency of the CJ-FEAST GSVDsolver.
相關內容
This paper focuses on representing the $L^{\infty}$-norm of finite-dimensional linear time-invariant systems with parameter-dependent coefficients. Previous studies tackled the problem in a non-parametric scenario by simplifying it to finding the maximum $y$-projection of real solutions $(x, y)$ of a system of the form $\Sigma=\{P=0, \, \partial P/\partial x=0\}$, where $P \in \Z[x, y]$. To solve this problem, standard computer algebra methods were employed and analyzed \cite{bouzidi2021computation}. In this paper, we extend our approach to address the parametric case. We aim to represent the "maximal" $y$-projection of real solutions of $\Sigma$ as a function of the given parameters. %a set of parameters $\alpha$. To accomplish this, we utilize cylindrical algebraic decomposition. This method allows us to determine the desired value as a function of the parameters within specific regions of parameter space.
A $3$-uniform hypergraph is a generalization of simple graphs where each hyperedge is a subset of vertices of size $3$. The degree of a vertex in a hypergraph is the number of hyperedges incident with it. The degree sequence of a hypergraph is the sequence of the degrees of its vertices. The degree sequence problem for $3$-uniform hypergraphs is to decide if a $3$-uniform hypergraph exists with a prescribed degree sequence. Such a hypergraph is called a realization. Recently, Deza \emph{et al.} proved that the degree sequence problem for $3$-uniform hypergraphs is NP-complete. Some special cases are easy; however, polynomial algorithms have been known so far only for some very restricted degree sequences. The main result of our research is the following. If all degrees are between $\frac{2n^2}{63}+O(n)$ and $\frac{5n^2}{63}-O(n)$ in a degree sequence $D$, further, the number of vertices is at least $45$, and the degree sum can be divided by $3$, then $D$ has a $3$-uniform hypergraph realization. Our proof is constructive and in fact, it constructs a hypergraph realization in polynomial time for any degree sequence satisfying the properties mentioned above. To our knowledge, this is the first polynomial running time algorithm to construct a $3$-uniform hypergraph realization of a highly irregular and dense degree sequence.
We analyze a goal-oriented adaptive algorithm that aims to efficiently compute the quantity of interest $G(u^\star)$ with a linear goal functional $G$ and the solution $u^\star$ to a general second-order nonsymmetric linear elliptic partial differential equation. The current state of the analysis of iterative algebraic solvers for nonsymmetric systems lacks the contraction property in the norms that are prescribed by the functional analytic setting. This seemingly prevents their application in the optimality analysis of goal-oriented adaptivity. As a remedy, this paper proposes a goal-oriented adaptive iteratively symmetrized finite element method (GOAISFEM). It employs a nested loop with a contractive symmetrization procedure, e.g., the Zarantonello iteration, and a contractive algebraic solver, e.g., an optimal multigrid solver. The various iterative procedures require well-designed stopping criteria such that the adaptive algorithm can effectively steer the local mesh refinement and the computation of the inexact discrete approximations. The main results consist of full linear convergence of the proposed adaptive algorithm and the proof of optimal convergence rates with respect to both degrees of freedom and total computational cost (i.e., optimal complexity). Numerical experiments confirm the theoretical results and investigate the selection of the parameters.
Most studies of adaptive algorithm behavior consider performance measures based on mean values such as the mean-square error. The derived models are useful for understanding the algorithm behavior under different environments and can be used for design. Nevertheless, from a practical point of view, the adaptive filter user has only one realization of the algorithm to obtain the desired result. This letter derives a model for the variance of the squared-error sample curve of the least-mean-square (LMS) adaptive algorithm, so that the achievable cancellation level can be predicted based on the properties of the steady-state squared error. The derived results provide the user with useful design guidelines.
Given an $m\times n$ binary matrix $M$ with $|M|=p\cdot mn$ (where $|M|$ denotes the number of 1 entries), define the discrepancy of $M$ as $\mbox{disc}(M)=\displaystyle\max_{X\subset [m], Y\subset [n]}\big||M[X\times Y]|-p|X|\cdot |Y|\big|$. Using semidefinite programming and spectral techniques, we prove that if $\mbox{rank}(M)\leq r$ and $p\leq 1/2$, then $$\mbox{disc}(M)\geq \Omega(mn)\cdot \min\left\{p,\frac{p^{1/2}}{\sqrt{r}}\right\}.$$ We use this result to obtain a modest improvement of Lovett's best known upper bound on the log-rank conjecture. We prove that any $m\times n$ binary matrix $M$ of rank at most $r$ contains an $(m\cdot 2^{-O(\sqrt{r})})\times (n\cdot 2^{-O(\sqrt{r})})$ sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank $r$ is at most $O(\sqrt{r})$.
An $(r, \delta)$-locally repairable code ($(r, \delta)$-LRC for short) was introduced by Prakash et al. for tolerating multiple failed nodes in distributed storage systems, and has garnered significant interest among researchers. An $(r,\delta)$-LRC is called an optimal code if its parameters achieve the Singleton-like bound. In this paper, we construct three classes of $q$-ary optimal cyclic $(r,\delta)$-LRCs with new parameters by investigating the defining sets of cyclic codes. Our results generalize the related work of \cite{Chen2022,Qian2020}, and the obtained optimal cyclic $(r, \delta)$-LRCs have flexible parameters. A lot of numerical examples of optimal cyclic $(r, \delta)$-LRCs are given to show that our constructions are capable of generating new optimal cyclic $(r, \delta)$-LRCs.
A recent line of work has shown the unconditional advantage of constant-depth quantum computation, or $\mathsf{QNC^0}$, over $\mathsf{NC^0}$, $\mathsf{AC^0}$, and related models of classical computation. Problems exhibiting this advantage include search and sampling tasks related to the parity function, and it is natural to ask whether $\mathsf{QNC^0}$ can be used to help compute parity itself. We study $\mathsf{AC^0\circ QNC^0}$ -- a hybrid circuit model where $\mathsf{AC^0}$ operates on measurement outcomes of a $\mathsf{QNC^0}$ circuit, and conjecture $\mathsf{AC^0\circ QNC^0}$ cannot achieve $\Omega(1)$ correlation with parity. As evidence for this conjecture, we prove: $\bullet$ When the $\mathsf{QNC^0}$ circuit is ancilla-free, this model achieves only negligible correlation with parity. $\bullet$ For the general (non-ancilla-free) case, we show via a connection to nonlocal games that the conjecture holds for any class of postprocessing functions that has approximate degree $o(n)$ and is closed under restrictions, even when the $\mathsf{QNC^0}$ circuit is given arbitrary quantum advice. By known results this confirms the conjecture for linear-size $\mathsf{AC^0}$ circuits. $\bullet$ Towards a switching lemma for $\mathsf{AC^0\circ QNC^0}$, we study the effect of quantum preprocessing on the decision tree complexity of Boolean functions. We find that from this perspective, nonlocal channels are no better than randomness: a Boolean function $f$ precomposed with an $n$-party nonlocal channel is together equal to a randomized decision tree with worst-case depth at most $\mathrm{DT}_\mathrm{depth}[f]$. Our results suggest that while $\mathsf{QNC^0}$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output, inaccessible to simple classical computation for solving decision problems.
We study the numerical approximation of multidimensional stochastic differential equations (SDEs) with distributional drift, driven by a fractional Brownian motion. We work under the Catellier-Gubinelli condition for strong well-posedness, which assumes that the regularity of the drift is strictly greater than $1-1/(2H)$, where $H$ is the Hurst parameter of the noise. The focus here is on the case $H<1/2$, allowing the drift $b$ to be a distribution. We compare the solution $X$ of the SDE with drift $b$ and its tamed Euler scheme with mollified drift $b^n$, to obtain an explicit rate of convergence for the strong error. This extends previous results where $b$ was assumed to be a bounded measurable function. In addition, we investigate the limit case when the regularity of the drift is equal to $1-1/(2H)$, and obtain a non-explicit rate of convergence. As a byproduct of this convergence, there exists a strong solution that is pathwise unique in a class of H\"older continuous solutions. The proofs rely on stochastic sewing techniques, especially to deduce new regularising properties of the discrete-time fractional Brownian motion. In the limit case, we introduce a critical Gr\"onwall-type lemma to quantify the error. We also present several examples and numerical simulations that illustrate our results.
In this paper we generalize the notion of $n$-equivalence relation introduced by Chen et al. in \cite{Chen2014} to classify constacyclic codes of length $n$ over a finite field $\Fq,$ where $q=p^r$ is a prime power, to the case of skew constacyclic codes without derivation. We call this relation $(n,\sigma)$-equivalence relation, where $n$ is the length of the code and $ \sigma$ is an automorphism of the finite field. We compute the number of $(n,\sigma)$-equivalence classes, and we give conditions on $ \lambda$ and $\mu$ for which $(\sigma, \lambda)$-constacyclic codes and $(\sigma, \lambda)$-constacyclic codes are equivalent with respect to our $(n,\sigma)$-equivalence relation. Under some conditions on $n$ and $q$ we prove that skew constacyclic codes are equivalent to cyclic codes. We also prove that when $q$ is even and $\sigma$ is the Frobenius autmorphism, skew constacyclic codes of length $n$ are equivalent to cyclic codes when $\gcd(n,r)=1$. Finally we give some examples as applications of the theory developed here.
We consider in this paper a numerical approximation of Poisson-Nernst-Planck-Navier- Stokes (PNP-NS) system. We construct a decoupled semi-discrete and fully discrete scheme that enjoys the properties of positivity preserving, mass conserving, and unconditionally energy stability. Then, we establish the well-posedness and regularity of the initial and (periodic) boundary value problem of the PNP-NS system under suitable assumptions on the initial data, and carry out a rigorous convergence analysis for the fully discretized scheme. We also present some numerical results to validate the positivity-preserving property and the accuracy of our scheme.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191