We introduce the concept of dot product representations of graphs, giving some motivations as well as surveying the previously known results. We extend these representations to more general fields, looking at the complex numbers, rational numbers, and finite fields. Finally, we study the behavior of dot product representations in field extensions.

In tropical algebras we substitute min or max for the typical addition and then substitute addition for multiplication. A dot product representation of a graph assigns each vertex of the graph a vector such that two edges are adjacent if and only if the dot product of their vectors is greater than some chosen threshold. The resultS of creating dot product representations of graphs using tropical algebras are examined. In particular we examine the tropical dot product dimensions of graphs and establish connections to threshold graphs and the threshold dimension of a graph.

We will introduce three new classes of graphs; namely bipartite dot product graphs, probe dot product graphs, and combinatorial orthogonal graphs. All of these representations were inspired by a vector representation known as a dot product representation. Given a bipartite graph G = (X, Y, E), the bipartite dot product representation of G is a function ƒ : X ∪ Y → Rk and a positive threshold t such that for any κ ∈ Χ and γ ∈ Υ , κγ ∈ ε if and only if f(κ) · f(γ) ≥ t. The minimum k such that a bipartite dot product representation exists for G is the bipartite dot product dimension of G, denoted bdp(G). We will show that such representations exist for all bipartite graphs as well as give an upper bound for the bipartite dot product dimension of any graph. We will also characterize the bipartite graphs of bipartite dot product dimension 1 by their forbidden subgraphs. An undirected graph G = (V, E) is a probe C graph if its vertex set can be parti-tioned into two sets, N (nonprobes) and P (probes) where N is independent and there exists E' ⊆ N × N such that G' = (V, E ∪ E) is a C graph. In this dissertation we introduce probe k-dot product graphs and characterize (at least partially) probe 1-dot product graphs in terms of forbidden subgraphs and certain 2-SAT formulas. These characterizations are given for the very different circumstances: when the partition into probes and nonprobes is given, and when the partition is not given. Vectors κ = (κ1, κ2, . . . , κn)T and γ = (γ1, γ2, . . . , γn)T are combinatorially orthogonal if |{i : κiγi = 0}| ≠ 1. An undirected graph G = (V, E) is a combinatorial orthogonal graph if there exists ƒ : V → Rn for some n ∈ Ν such that for any u, υ &Isin; V , uv ∉ E iff ƒ(u) and ƒ(v) are combinatorially orthogonal. These representations can also be limited to a mapping g : V → {0, 1}n such that for any u,v ∈ V , uv ∉ E iff g(u) · g(v) = 1. We will show that every graph has a combinatorial orthogonal representation. We will also state the minimum dimension necessary to generate such a representation for specific classes of graphs.

Searching for textual information has become an important activity on the web. To satisfy the rising demand and user expectations, search systems should be fast, scalable and deliver relevant results. To decide which objects should be retrieved, search systems should compare holistic meanings of queries and text document objects, as perceived by humans. Existing techniques do not enable correct comparison of composite holistic meanings like: "evidences on role of DR2 gene in development of diabetes in Caucasian population", which is composed of multiple elementary meanings: "evidence", "DR2 gene", etc. Thus these techniques can not discern objects that have a common set of keywords but convey different meanings. Hence we need new methods to compare composite meanings for superior search quality. In distributed search engines, for scalability, speed and efficiency, index entries should be systematically distributed across multiple index-server nodes based on the meaning of the objects. Furthermore, queries should be selectively sent to those index nodes which have relevant entries. This requires an overlay Semantic Routed Network which will route messages, based on meaning. This network will consist of fast response networking appliances called semantic routers. These appliances need to: (a) carry out sophisticated meaning comparison computations at high speed; and (b) have the right kind of behavior to automatically organize an optimal index system. This dissertation presents the following artifacts that enable the above requirements: (1) An algebraic theory, a design of a data structure and related techniques to efficiently compare composite meanings. (2) Algorithms and accelerator architectures for high speed meaning comparisons inside semantic routers and index-server nodes. (3) An overlay network to deliver search queries to the index nodes based on meanings. (4) Algorithms to construct a self-organizing, distributed meaning based index system. The proposed techniques can compare composite meanings ~105 times faster than an equivalent software code and existing hardware designs. Whereas, the proposed index organization approach can lead to 33% savings in number of servers and power consumption in a model search engine having 700,000 servers. Therefore, using all these techniques, it is possible to design a Semantic Routed Network which has a potential to improve search results and response time, while saving resources.

The original aim of the research was to investigate the conceptual dimensions of style in tonal music in order to provide grounds for an objective, measurable categorization of the phenomenon that could be construed as the basis of a scientific taxonomy of musical styles. However, this is a formidable task that surpasses the practical possibilities of the project, which would hence concentrate on creating the tools that would be needed for the following stage. A review of previous attempts to deal with style in music provided a number of guidelines for the process of dealing with the material. The project intends to avoid the subjectivity of musical analysis concentrating on music observable features. A database of 250 keyboard scores in MusicXML format was built to the purpose of covering the whole span of styles in tonal music, from which it should be possible to extract features to be used in style categorization. Early on, it became apparent that most meaningful pitch-related features are linked to scale degrees, thus essentially depending on functional labeling, requiring the knowledge of the key of the music as a point function. Different proposed alternatives to determine the key were considered and a method decided upon. Software was written and its effectiveness tested. The method proved successful in determining the instant key with as much precision as feasible. On this basis, it became possible to functionally label scale degrees and chords. This software constitutes the basic tool for the extraction of pitch-related features. As its first use, the software was applied to the score database in order to quantify the usage of scale degrees and chords. The results indisputably showed that tonal music can be characterized by specific proportions in the use of the different scale degrees, whereas the use of chords shows a constant increase in chromaticism. Part of the material of this work appeared in the Springer-Verlag's 2006 volume of Lecture Notes in Computer Science.

Most general purpose processors (GPP) and application specific processors (ASP) use the floating-point arithmetic due to its wide and precise number system. However, the floating-point operations require complex processes such as alignment, normalization and rounding. To reduce the overhead, fused floating-point arithmetic units are introduced. In this dissertation, improved architectures for three fused floating-point arithmetic units are proposed: 1) Fused floating-point add-subtract unit, 2) Fused floating-point two-term dot product unit, and 3) Fused floating-point three-term adder. Also, the three fused floating-point units are implemented for both single and double precision and evaluated in terms of the area, power consumption, latency and throughput. To improve the performance of the fused floating-point add-subtract unit, a new alignment scheme, fast rounding, two dual-path algorithms and pipelining are applied. The improved fused floating-point two-term dot product unit applies several optimizations: a new alignment scheme, early normalization and fast rounding, four-input leading zero anticipation (LZA), dual-path algorithm and pipelining. The proposed fused floating-point three-term adder applies a new exponent compare and significand alignment scheme, double reduction, early normalization and fast rounding, three-input LZA and pipelining to improve the performance. / text

Speeding up addition is the key to faster digital signal processing (DSP). This can be achieved by exploiting the properties of redundant number systems. Their expanded symbol (digit) alphabet gives them multiple representations for most values. Utilising redundant representations at the output of an adder permits addition to be performed without carry-propagation, yielding fast, constant time performance irrespective of the word length. A resource efficient implementation of this fast adder structure is developed that re-purposes the fast carry logic of low-cost field programmable gate arrays (FPGAs). Experiments confirm constant time addition and show that it outperforms binary ripple carry addition at word lengths of greater than 44 bits in a Xilinx Spartan 3 FPGA and 24 bits in an Altera Cyclone III FPGA. Redundancy also provides other properties that can be exploited for performance gain. Some redundant representations will have more zero-symbols than others. These maximise the opportunities to exploit the multiplicative absorbing and additive identity properties of zero that when exercised reduce superfluous calculations. A serial recoding algorithm is developed that generates a redundant representation for a specified value with as few nonzero symbols as possible. Unlike previously published methods, it accepts a wide specification of number systems including those with irregularly spaced symbol alphabets. A Markov analysis and analysis of the elementary cycles in the formulated state machine provides average and worst case measures for the tested number system. Typically, the average number of non-zero symbols is less than a third and the worst case is less than a half. Further to the increase in zero-symbols, zero-dominance is proposed as a new property of redundant number representations. It promotes a set of representations that have uniquely positioned zero-symbols, in a Pareto-optimal sense. This set covers all representations of a value and is used to select representations to optimise the calculation of a dot-product. The dot-product or vector-multiply is a fundamental operation in DSP, since it is employed in filtering, correlation and convolution. The nonzero partial products can be packed together, substantially reducing the calculation time. The application of redundant number systems provides a two-fold benefit. Firstly, the number of nonzero partial products is reduced. Secondly, a novel opportunity is identified to use the representations in the zero-dominant set to optimise the packing further, gaining an extra 18% improvement. An implementation of the proposed dot-product with partial product packing is developed for a Cyclone II FPGA. It outperforms a quad-multiplier binary implementation in throughput by 50% . Redundant number systems excel at increasing performance in particular DSP subsystems, those that are numerically intensive and consist of considerable accumulation. The conversion back to a binary result is the performance bottleneck in the DSP algorithm, taking a time proportional to a binary adder. Therefore, redundant number systems are best utilised when this conversion cost can be amortised over many fast redundant additions, which is typical in many DSP and communications applications.

O presente trabalho pretende aplicar o método de cálculo de componentes simétricas por produtos escalares de vetores espaciais para o cálculo dos sinais de referência de compensadores de perturbação. Outras metodologias de cálculo de corrente de referência são apresentadas, analisadas e comparadas com o método implementado. Uma revisão de vetores espaciais nos sistemas abc e 0 é feita para auxílio da explicação do método de extração de componentes simétricas. O método é inicialmente apresentado de forma generalista, de modo que é realizado o cálculo de componentes de sequência positiva, negativa e zero para um harmônico de ordem h. A autora apresenta algoritmos de exemplos práticos para uso em cálculo de corrente de referência incluindo as compensações de reativos da corrente fundamental, de harmônicos pré-selecionados e de desequilíbrios de carga. O método é analisado e validado por meio de simulações e resultados experimentais. / This work applies, for a disturbance compensator, a method for the calculation of the symmetrical components based on space vectors\' dot product. Other methods are presented, analyzed and compared with the proposed method. The symmetrical components calculation method is explained using a geometrical approach in abc and 0 basis. Initially, it is presented a general method that calculates the hth order positive, negative and zero sequence components of a current or voltage signal. Then, practical examples are presented for current compensation, which includes: fundamental reactive current compensation, fundamental negative sequence compensation and pre-selected order harmonics compensation. The method is analyzed and validated by simulation and experimental results.

O presente trabalho pretende aplicar o método de cálculo de componentes simétricas por produtos escalares de vetores espaciais para o cálculo dos sinais de referência de compensadores de perturbação. Outras metodologias de cálculo de corrente de referência são apresentadas, analisadas e comparadas com o método implementado. Uma revisão de vetores espaciais nos sistemas abc e 0 é feita para auxílio da explicação do método de extração de componentes simétricas. O método é inicialmente apresentado de forma generalista, de modo que é realizado o cálculo de componentes de sequência positiva, negativa e zero para um harmônico de ordem h. A autora apresenta algoritmos de exemplos práticos para uso em cálculo de corrente de referência incluindo as compensações de reativos da corrente fundamental, de harmônicos pré-selecionados e de desequilíbrios de carga. O método é analisado e validado por meio de simulações e resultados experimentais. / This work applies, for a disturbance compensator, a method for the calculation of the symmetrical components based on space vectors\' dot product. Other methods are presented, analyzed and compared with the proposed method. The symmetrical components calculation method is explained using a geometrical approach in abc and 0 basis. Initially, it is presented a general method that calculates the hth order positive, negative and zero sequence components of a current or voltage signal. Then, practical examples are presented for current compensation, which includes: fundamental reactive current compensation, fundamental negative sequence compensation and pre-selected order harmonics compensation. The method is analyzed and validated by simulation and experimental results.