In this paper we study two dimensional minimal linear code over the ring $\mathbb{Z}_{p^n}$(where $p$ is prime). We show that if the generator matrix $G$ of the two dimensional linear code $M$ contains $p^n+p^{n-1}$ column vector of the following type {\scriptsize{$u_{l_1}\begin{pmatrix} 1\\ 0 \end{pmatrix}$, $u_{l_2}\begin{pmatrix} 0\\1 \end{pmatrix}$, $u_{l_3}\begin{pmatrix} 1\\u_1 \end{pmatrix}$, $u_{l_4}\begin{pmatrix} 1\\u_2 \end{pmatrix}$,...,$u_{l_{p^n-p^{n-1}+2}} \begin{pmatrix} 1\\u_{p^n-p^{n-1}} \end{pmatrix}$, $u_{l_{p^n-p^{n-1}+3}}\begin{pmatrix} d_1 \\ 1 \end{pmatrix}$, $u_{l_{p^n-p^{n-1}+4}}\begin{pmatrix} d_2\\ 1 \end{pmatrix}$,..., $u_{l_{p^n+1}}\begin{pmatrix} d_{p^{n-1}-1}\\1 \end{pmatrix}$, $u_{l_{p^n+2}}\begin{pmatrix} 1\\d_1 \end{pmatrix}$, $u_{l_{p^n+3}}\begin{pmatrix} 1\\d_2 \end{pmatrix}$,...,$u_{l_{p^n+p^{n-1}}}\begin{pmatrix} 1 \\d_{p^{n-1}-1} \end{pmatrix}$}}, where $u_i$ and $d_j$ are distinct units and zero divisors respectively in the ring $\mathbb{Z}_{p^n}$ for $1\leq i \leq p^n+p^{n-1}$, $1\leq j \leq p^{n-1}-1$ and additionally, denote $u_{l_i}$ as units in $\mathbb{Z}_{p^n}$, then the module generated by $G$ is a minimal linear code. Also we show that if any one column vector of the above types are not present entirely in $G$, then the generated module is not a minimal linear code.
相關內容
In this paper, we study a $\tau$-matrix approximation based preconditioner for the linear systems arising from discretization of unsteady state Riesz space fractional diffusion equation with non-separable variable coefficients. The structure of coefficient matrices of the linear systems is identity plus summation of diagonal-times-multilevel-Toeplitz matrices. In our preconditioning technique, the diagonal matrices are approximated by scalar identity matrices and the Toeplitz matrices are approximated by {\tau}-matrices (a type of matrices diagonalizable by discrete sine transforms). The proposed preconditioner is fast invertible through the fast sine transform (FST) algorithm. Theoretically, we show that the GMRES solver for the preconditioned systems has an optimal convergence rate (a convergence rate independent of discretization stepsizes). To the best of our knowledge, this is the first preconditioning method with the optimal convergence rate for the variable-coefficients space fractional diffusion equation. Numerical results are reported to demonstrate the efficiency of the proposed method.
We consider additive Schwarz methods for boundary value problems involving the $p$-Laplacian. While existing theoretical estimates suggest a sublinear convergence rate for these methods, empirical evidence from numerical experiments demonstrates a linear convergence rate. In this paper, we narrow the gap between these theoretical and empirical results by presenting a novel convergence analysis. Firstly, we present a new convergence theory for additive Schwarz methods written in terms of a quasi-norm. This quasi-norm exhibits behavior akin to the Bregman distance of the convex energy functional associated with the problem. Secondly, we provide a quasi-norm version of the Poincar'{e}--Friedrichs inequality, which plays a crucial role in deriving a quasi-norm stable decomposition for a two-level domain decomposition setting. By utilizing these key elements, we establish the linear convergence.
In the present study, we consider the numerical method for Toeplitz-like linear systems arising from the $d$-dimensional Riesz space fractional diffusion equations (RSFDEs). We apply the Crank-Nicolson (CN) technique to discretize the temporal derivative and apply a quasi-compact finite difference method to discretize the Riesz space fractional derivatives. For the $d$-dimensional problem, the corresponding coefficient matrix is the sum of a product of a (block) tridiagonal matrix multiplying a diagonal matrix and a $d$-level Toeplitz matrix. We develop a sine transform based preconditioner to accelerate the convergence of the GMRES method. Theoretical analyses show that the upper bound of relative residual norm of the preconditioned GMRES method with the proposed preconditioner is mesh-independent, which leads to a linear convergence rate. Numerical results are presented to confirm the theoretical results regarding the preconditioned matrix and to illustrate the efficiency of the proposed preconditioner.
We consider the scenario of supervised learning in Deep Learning (DL) networks, and exploit the arbitrariness of choice in the Riemannian metric relative to which the gradient descent flow can be defined (a general fact of differential geometry). In the standard approach to DL, the gradient flow on the space of parameters (weights and biases) is defined with respect to the Euclidean metric. Here instead, we choose the gradient flow with respect to the Euclidean metric in the output layer of the DL network. This naturally induces two modified versions of the gradient descent flow in the parameter space, one adapted for the overparametrized setting, and the other for the underparametrized setting. In the overparametrized case, we prove that, provided that a rank condition holds, all orbits of the modified gradient descent drive the ${\mathcal L}^2$ cost to its global minimum at a uniform exponential convergence rate; one thereby obtains an a priori stopping time for any prescribed proximity to the global minimum. We point out relations of the latter to sub-Riemannian geometry. Moreover, we generalize the above framework to the situation in which the rank condition does not hold; in particular, we show that local equilibria can only exist if a rank loss occurs, and that generically, they are not isolated points, but elements of a critical submanifold of parameter space.
We study the problem of computing the Voronoi diagram of a set of $n^2$ points with $O(\log n)$-bit coordinates in the Euclidean plane in a substantially sublinear in $n$ number of rounds in the congested clique model with $n$ nodes. Recently, Jansson et al. have shown that if the points are uniformly at random distributed in a unit square then their Voronoi diagram within the square can be computed in $O(1)$ rounds with high probability (w.h.p.). We show that if a very weak smoothness condition is satisfied by an input set of $n^2$ points with $O(\log n)$-bit coordinates in the unit square then the Voronoi diagram of the point set within the unit square can be computed in $O(\log n)$ rounds in this model.
We improve the classical results by Brenner and Thom\'ee on rational approximations of operator semigroups. In the setting of Hilbert spaces, we introduce a finer regularity scale for initial data, provide sharper stability estimates, and obtain optimal approximation rates. Moreover, we strengthen a result due to Egert-Rozendaal on subdiagonal Pad\'e approximations of operator semigroups. Our approach is direct and based on the theory of the $\mathcal B$- functional calculus developed recently. On the way, we elaborate a new and simple approach to construction of the $\mathcal B$-calculus thus making the paper essentially self-contai
Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes $O(\sqrt{(\log n)/\varepsilon})$-approximation using $O(n^\varepsilon\log^{O(1)}n)$ maxflows for any $\varepsilon\in[\Theta(1/\log n),\Theta(1)]$. It works by solving the SDP relaxation of [Arora-Rao-Vazirani, STOC 2004] using the Multiplicative Weights Update algorithm (MW) of [Arora-Kale, JACM 2016]. To implement one MW step, Sherman approximately solves a multicommodity flow problem using another application of MW. Nested MW steps are solved via a certain ``chaining'' algorithm that combines results of multiple calls to the maxflow algorithm. We present an alternative approach that avoids solving the multicommodity flow problem and instead computes ``violating paths''. This simplifies Sherman's algorithm by removing a need for a nested application of MW, and also allows parallelization: we show how to compute $O(\sqrt{(\log n)/\varepsilon})$-approximation via $O(\log^{O(1)}n)$ maxflows using $O(n^\varepsilon)$ processors. We also revisit Sherman's chaining algorithm, and present a simpler version together with a new analysis.
In this second paper we solve the twisted conjugacy problem for even dihedral Artin groups, that is, groups with presentation $G(m) = \langle a,b \mid {}_{m}(a,b) = {}_{m}(b,a) \rangle$, where $m \geq 2$ is even, and $_{m}(a,b)$ is the word $abab\dots$ of length $m$. Similar to odd dihedral Artin groups, we prove orbit decidability for all subgroups $A \leq \mathrm{Aut}(G(m))$, which then implies that the conjugacy problem is solvable in extensions of even dihedral Artin groups.
In this paper we prove that the $\ell_0$ isoperimetric coefficient for any axis-aligned cubes, $\psi_{\mathcal{C}}$, is $\Theta(n^{-1/2})$ and that the isoperimetric coefficient for any measurable body $K$, $\psi_K$, is of order $O(n^{-1/2})$. As a corollary we deduce that axis-aligned cubes essentially "maximize" the $\ell_0$ isoperimetric coefficient: There exists a positive constant $q > 0$ such that $\psi_K \leq q \cdot \psi_{\mathcal{C}}$, whenever $\mathcal{C}$ is an axis-aligned cube and $K$ is any measurable set. Lastly, we give immediate applications of our results to the mixing time of Coordinate-Hit-and-Run for sampling points uniformly from convex bodies.
We present a deterministic $(1+\varepsilon)$-approximate maximum matching algorithm in $\mathsf{poly} 1/\varepsilon$ passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on $1/\varepsilon$. Our algorithm exponentially improves on the well-known randomized $(1/\varepsilon)^{O(1/\varepsilon)}$-pass algorithm from the seminal work by McGregor~[APPROX05], the recent deterministic algorithm by Tirodkar with the same pass complexity~[FSTTCS18]. Up to polynomial factors in $1/\varepsilon$, our work matches the state-of-the-art deterministic $(\log n / \log \log n) \cdot (1/\varepsilon)$-pass algorithm by Ahn and Guha~[TOPC18], that is allowed a dependence on the number of nodes $n$. Our result also makes progress on the Open Problem 60 at sublinear.info. Moreover, we design a general framework that simulates our approach for the streaming setting in other models of computation. This framework requires access to an algorithm computing an $O(1)$-approximate maximum matching and an algorithm for processing disjoint $(\mathsf{poly} 1 / \varepsilon)$-size connected components. Instantiating our framework in $\mathsf{CONGEST}$ yields a $\mathsf{poly}(\log{n}, 1/\varepsilon)$ round algorithm for computing $(1+\varepsilon$)-approximate maximum matching. In terms of the dependence on $1/\varepsilon$, this result improves exponentially state-of-the-art result by Lotker, Patt-Shamir, and Pettie~[LPSP15]. Our framework leads to the same quality of improvement in the context of the Massively Parallel Computation model as well.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191