Cyclic automorphic graph decompositions

Chapter 1 introduces the tools and mechanics necessary for this report. Basic definitions and topics of graph theory which pertain to the report and discussion of automorphic decompositions will be covered in brief detail. An automorphic decomposition D of a graph H by a graph G is a G-decomposition of H such that the intersection of graph (D) @H. H is called the automorhpic host, and G is the automorphic divisor. We seek to find classes of graphs that are automorphic divisors, specifically ones generated cyclically. Chapter 2 discusses the previous work done mainly by Beeler. It also discusses and gives in more detail examples of automorphic decompositions of graphs. Chapter 2 also discusses labelings and their direct relation to cyclic automorphic decompositions. We show basic classes of graphs, such as cycles, that are known to have certain labelings, and show that they also are automorphic divisors. In Chapter 3, we are concerned with 2-regular graphs, in particular rCm, r copies of the m-cycle. We seek to show that rCm has a ρ-labeling, and thus is an automorphic divisor for all r and m. we discuss methods including Skolem type difference sets to create cycle systems and their correlation to automorphic decompositions. In the Appendix, we give classes of graphs known to be graceful and our java code to generate ρ-labelings on rCm.

Effects of elevated atmospheric CO2 and O3 on wood density, antomical proerties and decomposition of Northern Hardwoods

Anthropogenic activities continue to drive atmospheric CO2 and O3 concentrations to levels higher than during the pre-industrial era. Accumulating evidence indicates that both elevated CO2 and elevated O3 could modify the quantity and biochemistry of woody plant biomass. Anatomical properties of woody plants are largely influenced by the activity of the cambium and the growth characteristics of wood cells, which are in turn influenced by a range of environmental factors. Hence, alterations in the concentrations of atmospheric CO2 and / or O3 could also impact wood anatomical properties. Many fungi derive their metabolic resources for growth from plant litter, including woody tissue, and therefore modifications in the quantity, biochemistry and anatomical properties of woody plants in response to elevated CO2 and / or O3 could impact the community of wood-decaying fungi and rates of wood decomposition. Consequently carbon and nutrient cycling and productivity of terrestrial ecosystem could also be impacted. Alterations in wood structure and biochemistry of woody plants could also impact wood density and subsequently impact wood quality. This dissertation examined the long term effects of elevated CO2 and / or O3 on wood anatomical properties, wood density, wood-decaying fungi and wood decomposition of northern hardwood tree species at the Aspen Free-Air CO2 and O3 Enrichment (Aspen FACE) project, near Rhinelander, WI, USA. Anatomical properties of wood varied significantly with species and aspen genotypes and radial position within the stem. Elevated CO2 did not have significant effects on wood anatomical properties in trembling aspen, paper birch or sugar maple, except for marginally increasing (P < 0.1) the number of vessels per square millimeter. Elevated O3 marginally or significantly altered vessel lumen diameter, cell wall area and vessel lumen area proportions depending on species and radial position. In line with the modifications in the anatomical properties, elevated CO2 and O3, alone, significantly modified wood density but effects were species and / or genotype specific. However, the effects of elevated CO2 and O3, alone, on wood anatomical properties and density were ameliorated when in combination. Wood species had a much greater impact on the wood-decaying fungal community and initial wood decomposition rate than did growth or decomposition of wood in elevated CO2 and / or O3. Polyporales, Agaricales, and Russulales were the dominant orders of fungi isolated. Based on the current results, future higher levels of CO2 and O3 may have moderate effects on wood quality of northern hardwoods, but for utilization purposes these may not be considered significant. However, wood-decaying fungal community composition and decomposition of northern hardwoods may be altered via shifts in species and / or genotype composition under future higher levels of CO2 and O3.

Enumeration of inequivalent cycle decompositions

A k-cycle decomposition of order n is a partition of the edges of the complete graph on n vertices into k-cycles. In this report a backtracking algorithm is developed to count the number of inequivalent k-cycle decompositions of order n.

Hamilton decompositions of 6-regular abelian Cayley graphs

In 1969, Lovasz asked whether every connected, vertex-transitive graph has a Hamilton path. This question has generated a considerable amount of interest, yet remains vastly open. To date, there exist no known connected, vertex-transitive graph that does not possess a Hamilton path. For the Cayley graphs, a subclass of vertex-transitive graphs, the following conjecture was made: Weak Lovász Conjecture: Every nontrivial, finite, connected Cayley graph is hamiltonian. The Chen-Quimpo Theorem proves that Cayley graphs on abelian groups flourish with Hamilton cycles, thus prompting Alspach to make the following conjecture: Alspach Conjecture: Every 2k-regular, connected Cayley graph on a finite abelian group has a Hamilton decomposition. Alspach’s conjecture is true for k = 1 and 2, but even the case k = 3 is still open. It is this case that this thesis addresses. Chapters 1–3 give introductory material and past work on the conjecture. Chapter 3 investigates the relationship between 6-regular Cayley graphs and associated quotient graphs. A proof of Alspach’s conjecture is given for the odd order case when k = 3. Chapter 4 provides a proof of the conjecture for even order graphs with 3-element connection sets that have an element generating a subgroup of index 2, and having a linear dependency among the other generators. Chapter 5 shows that if Γ = Cay(A, {s1, s2, s3}) is a connected, 6-regular, abelian Cayley graph of even order, and for some1 ≤ i ≤ 3, Δi = Cay(A/(si), {sj1 , sj2}) is 4-regular, and Δi ≄ Cay(ℤ3, {1, 1}), then Γ has a Hamilton decomposition. Alternatively stated, if Γ = Cay(A, S) is a connected, 6-regular, abelian Cayley graph of even order, then Γ has a Hamilton decomposition if S has no involutions, and for some s ∈ S, Cay(A/(s), S) is 4-regular, and of order at least 4. Finally, the Appendices give computational data resulting from C and MAGMA programs used to generate Hamilton decompositions of certain non-isomorphic Cayley graphs on low order abelian groups.

HIGH PERFORMANCE, LOW COST SUBSPACE DECOMPOSITION AND POLYNOMIAL ROOTING FOR REAL TIME DIRECTION OF ARRIVAL ESTIMATION: ANALYSIS AND IMPLEMENTATION

This thesis develops high performance real-time signal processing modules for direction of arrival (DOA) estimation for localization systems. It proposes highly parallel algorithms for performing subspace decomposition and polynomial rooting, which are otherwise traditionally implemented using sequential algorithms. The proposed algorithms address the emerging need for real-time localization for a wide range of applications. As the antenna array size increases, the complexity of signal processing algorithms increases, making it increasingly difficult to satisfy the real-time constraints. This thesis addresses real-time implementation by proposing parallel algorithms, that maintain considerable improvement over traditional algorithms, especially for systems with larger number of antenna array elements. Singular value decomposition (SVD) and polynomial rooting are two computationally complex steps and act as the bottleneck to achieving real-time performance. The proposed algorithms are suitable for implementation on field programmable gated arrays (FPGAs), single instruction multiple data (SIMD) hardware or application specific integrated chips (ASICs), which offer large number of processing elements that can be exploited for parallel processing. The designs proposed in this thesis are modular, easily expandable and easy to implement. Firstly, this thesis proposes a fast converging SVD algorithm. The proposed method reduces the number of iterations it takes to converge to correct singular values, thus achieving closer to real-time performance. A general algorithm and a modular system design are provided making it easy for designers to replicate and extend the design to larger matrix sizes. Moreover, the method is highly parallel, which can be exploited in various hardware platforms mentioned earlier. A fixed point implementation of proposed SVD algorithm is presented. The FPGA design is pipelined to the maximum extent to increase the maximum achievable frequency of operation. The system was developed with the objective of achieving high throughput. Various modern cores available in FPGAs were used to maximize the performance and details of these modules are presented in detail. Finally, a parallel polynomial rooting technique based on Newton’s method applicable exclusively to root-MUSIC polynomials is proposed. Unique characteristics of root-MUSIC polynomial’s complex dynamics were exploited to derive this polynomial rooting method. The technique exhibits parallelism and converges to the desired root within fixed number of iterations, making this suitable for polynomial rooting of large degree polynomials. We believe this is the first time that complex dynamics of root-MUSIC polynomial were analyzed to propose an algorithm. In all, the thesis addresses two major bottlenecks in a direction of arrival estimation system, by providing simple, high throughput, parallel algorithms.

ANALYSIS AND VISUALIZATION OF FLOW FIELDS USING INFORMATION-THEORETIC TECHNIQUES AND GRAPH-BASED REPRESENTATIONS

Three-dimensional flow visualization plays an essential role in many areas of science and engineering, such as aero- and hydro-dynamical systems which dominate various physical and natural phenomena. For popular methods such as the streamline visualization to be effective, they should capture the underlying flow features while facilitating user observation and understanding of the flow field in a clear manner. My research mainly focuses on the analysis and visualization of flow fields using various techniques, e.g. information-theoretic techniques and graph-based representations. Since the streamline visualization is a popular technique in flow field visualization, how to select good streamlines to capture flow patterns and how to pick good viewpoints to observe flow fields become critical. We treat streamline selection and viewpoint selection as symmetric problems and solve them simultaneously using the dual information channel [81]. To the best of my knowledge, this is the first attempt in flow visualization to combine these two selection problems in a unified approach. This work selects streamline in a view-independent manner and the selected streamlines will not change for all viewpoints. My another work [56] uses an information-theoretic approach to evaluate the importance of each streamline under various sample viewpoints and presents a solution for view-dependent streamline selection that guarantees coherent streamline update when the view changes gradually. When projecting 3D streamlines to 2D images for viewing, occlusion and clutter become inevitable. To address this challenge, we design FlowGraph [57, 58], a novel compound graph representation that organizes field line clusters and spatiotemporal regions hierarchically for occlusion-free and controllable visual exploration. We enable observation and exploration of the relationships among field line clusters, spatiotemporal regions and their interconnection in the transformed space. Most viewpoint selection methods only consider the external viewpoints outside of the flow field. This will not convey a clear observation when the flow field is clutter on the boundary side. Therefore, we propose a new way to explore flow fields by selecting several internal viewpoints around the flow features inside of the flow field and then generating a B-Spline curve path traversing these viewpoints to provide users with closeup views of the flow field for detailed observation of hidden or occluded internal flow features [54]. This work is also extended to deal with unsteady flow fields. Besides flow field visualization, some other topics relevant to visualization also attract my attention. In iGraph [31], we leverage a distributed system along with a tiled display wall to provide users with high-resolution visual analytics of big image and text collections in real time. Developing pedagogical visualization tools forms my other research focus. Since most cryptography algorithms use sophisticated mathematics, it is difficult for beginners to understand both what the algorithm does and how the algorithm does that. Therefore, we develop a set of visualization tools to provide users with an intuitive way to learn and understand these algorithms.

The Processing of Aluminum Gasarites via Thermal Decomposition of Interstitial Hydrides

Gasarite structures are a unique type of metallic foam containing tubular pores. The original methods for their production limited them to laboratory study despite appealing foam properties. Thermal decomposition processing of gasarites holds the potential to increase the application of gasarite foams in engineering design by removing several barriers to their industrial scale production. The following study characterized thermal decomposition gasarite processing both experimentally and theoretically. It was found that significant variation was inherent to this process therefore several modifications were necessary to produce gasarites using this method. Conventional means to increase porosity and enhance pore morphology were studied. Pore morphology was determined to be more easily replicated if pores were stabilized by alumina additions and powders were dispersed evenly. In order to better characterize processing, high temperature and high ramp rate thermal decomposition data were gathered. It was found that the high ramp rate thermal decomposition behavior of several hydrides was more rapid than hydride kinetics at low ramp rates. This data was then used to estimate the contribution of several pore formation mechanisms to the development of pore structure. It was found that gas-metal eutectic growth can only be a viable pore formation mode if non-equilibrium conditions persist. Bubble capture cannot be a dominant pore growth mode due to high bubble terminal velocities. Direct gas evolution appears to be the most likely pore formation mode due to high gas evolution rate from the decomposing particulate and microstructural pore growth trends. The overall process was evaluated for its economic viability. It was found that thermal decomposition has potential for industrialization, but further refinements are necessary in order for the process to be viable.

INTERACTIVE EFFECTS OF CLIMATE CHANGE AND FUNGAL COMMUNITIES ON THE DECOMPOSITION OF WOOD-DERIVED CARBON IN FOREST SOILS

Soils are the largest sinks of carbon in terrestrial ecosystems. Soil organic carbon is important for ecosystem balance as it supplies plants with nutrients, maintains soil structure, and helps control the exchange of CO2 with the atmosphere. The processes in which wood carbon is stabilized and destabilized in forest soils is still not understood completely. This study attempts to measure early wood decomposition by different fungal communities (inoculation with pure colonies of brown or white rot, or the original microbial community) under various interacting treatments: wood quality (wood from +CO2, +CO2+O3, or ambient atmosphere Aspen-FACE treatments from Rhinelander, WI), temperature (ambient or warmed), soil texture (loamy or sandy textured soil), and wood location (plot surface or buried 15cm below surface). Control plots with no wood chips added were also monitored throughout the study. By using isotopically-labelled wood chips from the Aspen-FACE experiment, we are able to track wood-derived carbon losses as soil CO2 efflux and as leached dissolved organic carbon (DOC). We analyzed soil water for chemical characteristics such as, total phenolics, SUVA254, humification, and molecular size. Wood chip samples were also analyzed for their proportion of lignin:carbohydrates using FTIR analysis at three time intervals throughout 12 months of decomposition. After two years of measurements, the average total soil CO2 efflux rates were significantly different depending on wood location, temperature, and wood quality. The wood-derived portion soil CO2 efflux also varied significantly by wood location, temperature, and wood quality. The average total DOC and the wood-derived portion of DOC differed between inoculation treatments, wood location, and temperature. Soil water chemical characteristics varied significantly by inoculation treatments, temperature, and wood quality. After 12 months of decomposition the proportion of lignin:carbohydrates varied significantly by inoculation treatment, with white rot having the only average proportional decrease in lignin:carbohydrates. Both soil CO2 efflux and DOC losses indicate that wood location is important. Carbon losses were greater from surface wood chips compared with buried wood chips, implying the importance of buried wood for total ecosystem carbon stabilization. Treatments associated with climate change also had an effect on the level of decomposition. DOC losses, soil water characteristics, and FTIR data demonstrate the importance of fungal community on the degree of decomposition and the resulting byproducts found throughout the soil.