Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecursive Structure and Bandwidth of Hales-Numbered Hypercube
152
0
0.0
(
0
)
Added by
Xiaohan Wang
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Hales numbered $n$-dimensional hypercube and the corresponding adjacency matrix exhibit interesting recursive structures in $n$. These structures lead to a very simple proof of the well-known bandwidth formula for hypercube, whose proof was thought to be surprisingly difficult. A related problem called hypercube antibandwidth, for which Harper proposed an algorithm, is also reexamined in the light of the above recursive structures, and a close form solution is found.
rate research
Read More
Partly in service of exploring the formal basis for Georgetown Universitys AvesTerra database structure, we formalize a recursive hypergraph data structure, which we call an ubergraph.
We determine the asymptotics of the number of independent sets of size $lfloor beta 2^{d-1} rfloor$ in the discrete hypercube $Q_d = {0,1}^d$ for any fixed $beta in [0,1]$ as $d to infty$, extending a result of Galvin for $beta in [1-1/sqrt{2},1]$. Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard core model at any fixed fugacity $lambda>0$. In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.
We present a high-bandwidth, lightweight, and nonlinear output tracking technique for soft actuators that combines parsimonious recursive layers for forward output predictions and online optimization using Newton-Raphson. This technique allows for reduced model sizes and increased control loop frequencies when compared with conventional RNN models. Experimental results of this controller prototype on a single soft actuator with soft positional sensors indicate effective tracking of referenced spatial trajectories and rejection of mechanical and electromagnetic disturbances. These are evidenced by root mean squared path tracking errors (RMSE) of 1.8mm using a fully connected (FC) substructure, 1.62mm using a gated recurrent unit (GRU) and 2.11mm using a long short term memory (LSTM) unit, all averaged over three tasks. Among these models, the highest flash memory requirement is 2.22kB enabling co-location of controller and actuator.
This paper is devoted to the study of the dynamics of a discrete system related to some self stabilizing protocol on a ring of processors.
A new fixed (non-adaptive) recursive scheme for multigrid algorithms is introduced. Governed by a positive parameter $kappa$ called the cycle counter, this scheme generates a family of multigrid cycles dubbed $kappa$-cycles. The well-known $V$-cycle, $F$-cycle, and $W$-cycle are shown to be particular members of this rich $kappa$-cycle family, which satisfies the property that the total number of recursive calls in a single cycle is a polynomial of degree $kappa$ in the number of levels of the cycle. This broadening of the scope of fixed multigrid cycles is shown to be potentially significant for the solution of some large problems on platforms, such as GPU processors, where the overhead induced by recursive calls may be relatively significant. In cases of problems for which the convergence of standard $V$-cycles or $F$-cycles (corresponding to $kappa=1$ and $kappa=2$, respectively) is particularly slow, and yet the cost of $W$-cycles is very high due to the large number of recursive calls (which is exponential in the number of levels), intermediate values of $kappa$ may prove to yield significantly faster run-times. This is demonstrated in examples where $kappa$-cycles are used for the solution of rotated anisotropic diffusion problems, both as a stand-alone solver and as a preconditioner. Moreover, a simple model is presented for predicting the approximate run-time of the $kappa$-cycle, which is useful in pre-selecting an appropriate cycle counter for a given problem on a given platform. Implementing the $kappa$-cycle requires making just a small change in the classical multigrid cycle.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
