Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation of an undirected graph, has rank equal to the maximum number of vertices covered by a matching in the associated graph. The branching matrix, a representation of a directed graph, has rank equal to the maximum number of vertices covered by a branching in the associated graph. A mixed graph has both undirected and directed edges, and the matching forest problem for mixed graphs, introduced by Giles, is a generalization of the matching problem and the branching problem. A mixed graph can be represented by the matching forest matrix, and the rank of the matching forest matrix is related to the size of a matching forest in the associated mixed graph. The Tutte matrix and the branching matrix have indeterminate entries, and we describe algorithms that evaluate the indeterminates as rationals in such a way that the rank of the evaluated matrix is equal to the rank of the indeterminate matrix. Matroids in the context of graphs are discussed, and matroid formulations for the matching, branching, and matching forest problems are given.

The reliability of networking and communication systems is vital for the nation's economy and security. Optical and cellular networks have become a critical infrastructure and are indispensable in emergency situations. This dissertation outlines methods for analyzing such infrastructures in the presence of catastrophic failures, such as a hurricane, as well as accidental failures of one or more components. Additionally, it presents a method for protecting against the loss of a single link in a multicast network along with a technique that enables wireless clients to efficiently recover lost data sent by their source through collaborative information exchange. Analysis of a network's reliability during a natural disaster can be assessed by simulating the conditions in which it is expected to perform. This dissertation conducts the analysis of a cellular infrastructure in the aftermath of a hurricane through Monte-Carlo sampling and presents alternative topologies which reduce resulting loss of calls. While previous research on restoration mechanisms for large-scale networks has mostly focused on handling the failures of single network elements, this dissertation examines the sampling methods used for simulating multiple failures. We present a quick method of nding a lower bound on a network's data loss through enumeration of possible cuts as well as an efficient method of nding a tighter lower bound through genetic algorithms leveraging the niching technique. Mitigation of data losses in a multicast network can be achieved by adding redundancy and employing advanced coding techniques. By using Maximum Rank Distance (MRD) codes at the source, a provider can create a parity packet which is e ectively linearly independent from the source packets such that all packets may be transmitted through the network using the network coding technique. This allows all sinks to recover all of the original data even with the failure of an edge within the network. Furthermore, this dissertation presents a method that allows a group of wireless clients to cooperatively recover from erasures (e.g., due to failures) by using the index coding techniques.

With the extension of the World Wide Web, more than 7 million new pages being exploited each day, the problem of information overload due to a large number of coping, spreading and sharing causes the decreasing information quantity, diverse format of information and low quality of information. More researchers research what methods including search and recommendation can help users gather the critical topics. Whatever methods use historical purchasing or browsing data to find the proper information usually, can not considering all attributes affecting decision results. Therefore, the research uses Analytic Hierarchy Process belonging Multiple Critical Decision Theory to develop recommendation system. Providing a single, easy understand model, using hierarchic structuring reflecting the nature tendency of the mind, considering all attributes affecting decision results, Analytic Hierarchy Process takes into consideration the relative priorities and select the best alternative. Furthermore, it can show the subjective consciousness of the user in a structure way and assist designer to determine a more rational and conformable judgment. Based on Analytic Hierarchy Process, the commerce recommendation system expects to help user to find more satisfactory merchandise. It is found that the recommendation system using Analytic Hierarchy Process finds the accurate products for user and gets the higher satisfaction. However, the operation satisfaction is not higher that rank-based but still in available and satisfaction scope.

Recently, Dawson and Feinstein showed that a Banach algebra integral extension B of a commutative Banach algebra A of topological stable rank one is again of topological stable rank one. In this thesis, we provide a partial converse to this statement: If an Arens-Hoffman extension A® of a commutative C*-algebra A has topological stable rank one then A has topological stable rank one.

This thesis is devoted to the analysis of relations between two major conjectures in the theory of groups of finite Morley rank. One of them is the Cherlin-Zil&#039 / ber Algebraicity Conjecture which states that infinite simple groups of finite Morley rank are isomorphic to simple algebraic groups over algebraically closed fields. The other conjecture is due to Hrushovski and it states that a generic automorphism of a simple group of finite Morley rank has pseudofinite group of fixed points. Hrushovski showed that the Cherlin-Zil&#039 / ber Conjecture implies his conjecture. Proving his Conjecture and reversing the implication would provide a new efficient approach to prove the Cherlin-Zil&#039 / ber Conjecture. This thesis proposes an approach to derive a proof of the Cherlin-Zil&#039 / ber Conjecture from Hrushovski&#039 / s Conjecture and contains a proof of a step in that direction. Firstly, we show that John S. Wilson&#039 / s classification theorem for simple pseudofinite groups can be adapted for definably simple non-abelian pseudofinite groups of finite centralizer dimension. Combining this result with recent related developments, we identify definably simple non-abelian pseudofinite groups with Chevalley or twisted Chevalley groups over pseudofinite fields. After that in the context of Hrushovski&#039 / s Conjecture, in a purely algebraic set-up, we show that the pseudofinite group of fixed points of a generic automorphism is actually an extension of a Chevalley group or a twisted Chevalley group over a pseudofinite field.

In this paper, we prove that the simulation method for interval-censored data proposed by Fay (1999) is consistent in the sense that if we select a sample, then the estimate obtained from Turnbulls (1974) EM algorithm will converge to the true parameter when the sample size tends to infinity. We also propose a non-parametric rank test for interval-censored data to determine whether two populations come from the same distribution. Simulation result shows that the proposed test statistics performs pretty satisfactory.

I have investigated the social grooming in kinship, rank, age and seasonal change among adult female Formosan macaques (Macaca cyclopis) that inhabit Mt. Longevity, Kaohsiung. The major study groups were C and Cd groups. Field observations were conducted from August 2000 to February 2003 covering three mating seasons and two non-mating seasons. The observations covered a total of 188 work days including 1248.8 hours. I actually had recorded C group for 660.6 hours, and Cd group for 244.5 hours. During my study, C group consisted of 8-13 adult males and 14-15 adult females, while group Cd had 1-3 adult males and 2-4 adult females. In order to analyze grooming data, I divided 15 adult females into sub-groups such as dominant/ submissive groups, old (>13) /young age (5-12), relative higher/lower ranking and related/unrelated. I have also divided adult males into troop-males and periphery males. Adult female allo-grooming activities accounted for 37.62% ¡Ó 13.59 (n = 15) of the behaviors in the daytime. I also found that adult females grooming infants and juveniles were greater than received from them (p < 0.001). The social grooming among adult females occurred mainly during non-mating seasons and its frequency was 2.12 times of mating seasons. Regardless of mating or non-mating seasons, the frequency of grooming among related females was significantly higher than among unrelated females (both p < 0.001). In addition, kinship affected the grooming frequency among female macaques with relative lower or higher ranking females during mating seasons (p < 0.05), while the dominant rank did not have the effect. However, the highest grooming frequency occurred in the high-ranking females who groomed relative lower ranking females within relatives (0.38 ¡Ó 0.40 bouts / 100 scans, n = 7). During non-mating seasons, kinship affected the grooming frequency among female macaques with relative lower ranking females (p < 0.05); the highest grooming frequency occurred in the old females who groomed relative lower ranking females within relatives (1.57 ¡Ó 1.74 bouts / 100 scans, n = 8). Moreover, seasons (mating or non-mating) and kinship relationship had significant effects on grooming frequencies among female macaques (both giving and receiving p < 0.01), as well as on the grooming frequency of females groomed with relative lower ranking females (p < 0.01). The highest grooming frequency occurred on females groomed with relative lower ranking females within relatives during non-mating seasons (1.25 ¡Ó 1.48 bouts / 100 scans, n = 11). Without kinship relationship, low-ranking females groomed relative higher ranking females more frequent than high-ranking females did (p < 0.05). Within adult females, 65% of social grooming was among relatives. However, 40% of adult females groomed equally with related and unrelated females, while 20% disproportionately groomed more with unrelated females than with related females. The grooming was kin-biased for 40%. About 8.68% of social grooming among unrelated females was being reciprocated. On the other hand, the ratio of related grooming female partners to the total number of available related females was higher than that with unrelated females (p < 0.05). It also indicated that the ratio of each female received grooming from high-ranking grooming partners was higher than that from low-ranking females (p < 0.01).On the other hand, the ratio of the number of old or young grooming partners of adult females had similar values. The grooming frequency of adult females gave or received from adult males during mating seasons was higher than non-mating seasons (both p < 0.05) while high-rank females groomed adult males more than low-rank females did. The socionomic sex ratios of these two social groups were similar during mating seasons (AM:AF = 1:1.8). Both troop and periphery males had significantly higher frequency of social grooming with adult females in mating seasons than in non-mating seasons. The types of males and social groups had significant effects on the allogrooming frequency among adult males in mating seasons (p < 0.05) but not in non-mating seasons (p > 0.1). Moreover, troop males had higher grooming partners than periphery males. Major grooming partners of troop males were adult females regardless of the seasons. Subordinate males were mostly the receivers in the grooming dyads with dominant males in the mating seasons, but the relationships changed during non-mating seasons. Agonistic interactions occurred mainly during mating seasons and its frequency among periphery males was 1.8 times of troop males (p < 0.05). The preference grooming sites between allo-grooming and auto-grooming of C and Cd groups had varied significantly (p < 0.001). The back region was the preferred grooming site in allo-grooming of C and Cd group and the ano-genital region was the least groomed site. In auto-grooming, monkeys paid much attention to the legs ignoring the back and face. The result indicated that when the adult individuals groomed the head, back and face which showed significant difference in the frequency among AM and AF (p < 0.05). The related female adults groomed head more frequently than unrelated female adults (p < 0.05), but dominance rank and age-class did not apparently affect the corresponding values for the frequency of grooming sites among adult females (both p > 0.1). The results indicated that social grooming among adult females took place more often during non-mating seasons, and more often in kin-related females than unrelated females. Moreover, the dominant females were likely to groom related females. Therefore social grooming among kin-related females may reinforce relationships while reciprocal grooming of unrelated females may serve to form alliance or ranking promotion in the social group. On the other hand, social grooming between adult male and female macaques more frequent in mating seasons than in non-mating seasons. This showed that adult male Formosan macaques employed complex strategies to achieve reproductive success. Nonetheless, the periphery males had more male grooming partners than troop males did which seemingly to enhance male coalitions.

This dissertation provides the first known examples of finite co-volume Kleinian groups which have co- final towers of finite index subgroups with positive rank gradient. We prove that if the fundamental group of an orientable finite volume hyperbolic 3-manifold has fi nite index in the reflection group of a right-angled ideal polyhedron in H^3 then it has a co-fi nal tower of fi nite sheeted covers with positive rank gradient. The manifolds we provide are also known to have co- final towers of covers with zero rank gradient. We also prove that the reflection groups of compact right-angled hyperbolic polyhedra satisfying mild conditions have co-fi nal towers of fi nite sheeted covers with positive rank gradient. / text

Third generation full-waveform (FW) LIDAR systems image an entire scene by emitting laser pulses in particular directions and measuring the echoes. Each of these echoes provides range measurements about the objects intercepted by the laser pulse along a specified direction. By scanning through a specified region using a series of emitted pulses and observing their echoes, connected 1D profiles of 3D scenes can be readily obtained. This extra information has proven helpful in providing additional insight into the scene structure which can be used to construct effective characterizations and classifications. Unfortunately, massive amounts of data are typically collected which impose storage, processing and transmission limitations. To address these problems, a number of compression approaches have been developed in the literature. These, however, generally require the initial acquisition of large amounts of data only to later discard most of it by exploiting redundancies, thus sampling inefficiently. Based on this, our main goal is to apply efficient and effective LIDAR sampling schemes that achieve acceptable reconstruction quality of the 3D scenes. To achieve this goal, we propose on using compressive sampling by emitting pulses only into random locations within the scene and collecting only the corresponding returned FW signals. Under this framework, the number of emissions would typically be much smaller than what traditional LIDAR systems require. Application of this requires, however, that scenes contain many degrees of freedom. Fortunately, such a requirement is satisfied in most natural and man-made scenes. Here, we propose to use a measure of rank as the measure of degrees of freedom. To recover the connected 1D profiles of the 3D scene, matrix completion is applied to the tensor slices. In this paper, we test our approach by showing that recovery of compressively sampled 1D profiles of actual 3D scenes is possible using only a subset of measurements.

Quantum chemistry is plagued by the presence of high-rank quantities, stemming from the N-body nature of the electronic Schrödinger equation. These high-rank quantities present a significant mathematical and computational barrier to the computation of chemical observables, and also drastically complicate the pedagogical understanding of important interactions between particles in a molecular system. The application of physically-motivated rank reduction approaches can help address these to problems. This thesis details recent efforts to apply rank reduction techniques in both of these arenas. With regards to computational tractability, the representation of the 1/r Coulomb repulsion between electrons is a critical stage in the solution of the electronic Schrödinger equation. Typically, this interaction is encapsulated via the order-4 electron repulsion integral (ERI) tensor, which is a major bottleneck in terms of generation, manipulation, and storage. Many rank reduction techniques for the ERI tensor have been proposed to ameliorate this bottleneck, most notably including the order-3 density fitting (DF) and pseudospectral (PS) representations. Here we detail a new and uniquely powerful factorization - tensor hypercontraction (THC). THC decomposes the ERI tensor as a product of five order-2 matrices (the first wholly order-2 compression proposed for the ERI) and offers great flexibility for low-scaling algorithms for the manipulations of the ERI tensor underlying electronic structure theory. THC is shown to be physically-motivated, markedly accurate, and uniquely efficient for some of the most difficult operations encountered in modern quantum chemistry. On the front of chemical understanding of electronic structure theory, we present our recent work in developing robust two-body partitions for ab initio computations of intermolecular interactions. Noncovalent interactions are the critical and delicate forces which govern such important processes as drug-protein docking, enzyme function, crystal packing, and zeolite adsorption. These forces arise as weak residual interactions leftover after the binding of electrons and nuclei into molecule, and, as such, are extremely difficult to accurately quantify or systematically understand. Symmetry-adapted perturbation theory (SAPT) provides an excellent approach to rigorously compute the interaction energy in terms of the physically-motivated components of electrostatics, exchange, induction, and dispersion. For small intermolecular dimers, this breakdown provides great insight into the nature of noncovalent interactions. However, SAPT abstracts away considerable details about the N-body interactions between particles on the two monomers which give rise to the interaction energy components. In the work presented herein, we step back slightly and extract an effective 2-body interaction for each of the N-body SAPT terms, rather than immediately tracing all the way down to the order-0 interaction energy. This effective order-2 representation of the order-N SAPT interaction allows for the robust assignment of interaction energy contributions to pairs of atoms or functional groups (the A-SAPT or F-SAPT partitions), allowing one to discuss the interaction in terms of atom- or functional-group-pairwise interactions. These A-SAPT and F-SAPT partitions can provide deep insight into the origins of complicated noncovalent interactions, e.g., by clearly shedding light on the long-contested question of the nature of the substituent effect in substituted sandwich benzene dimers.