Numerically Exact Study of Polarizabilities and Hyperpolarizabilities of Correlated Conjugated Organic Models

Polarizabilities and Hyperpolarizabilities of conjugated organic chains are calculated using correlated model Hamiltonians. While correlations reduce the Polarizabilities and extend the range of linear response, the Hyperpolarizabilities essentially are unaffected by the same. This explains the apparently large Hyperpolarizabilities of conjugated electronic systems.

Exact static polarizabilities of correlated finite model systems

A finite-field method for calculating exact polarizabilities of correlated conjugated model systems within the valence bond (VB) framework is presented. The correlations reduce the polarizabilities from their noninteracting values and extend the range of linearity to higher external fields. The large nonlinear polarizabilities observed in strongly correlated conjugated organic molecules cannot be directly attributed to electron correlations. The method described can be employed to calculate static polarizabilities for any desired state of a correlated system.

Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

Exact path-integral evaluation of the heat distribution function of a trapped Brownian oscillator

Using path integrals, we derive an exact expression-valid at all times t-for the distribution P(Q,t) of the heat fluctuations Q of a Brownian particle trapped in a stationary harmonic well. We find that P(Q, t) can be expressed in terms of a modified Bessel function of zeroth order that in the limit t > infinity exactly recovers the heat distribution function obtained recently by Imparato et al. Phys. Rev. E 76, 050101(R) (2007)] from the approximate solution to a Fokker-Planck equation. This long-time result is in very good agreement with experimental measurements carried out by the same group on the heat effects produced by single micron-sized polystyrene beads in a stationary optical trap. An earlier exact calculation of the heat distribution function of a trapped particle moving at a constant speed v was carried out by van Zon and Cohen Phys. Rev. E 69, 056121 (2004)]; however, this calculation does not provide an expression for P(Q, t) itself, but only its Fourier transform (which cannot be analytically inverted), nor can it be used to obtain P(Q, t) for the case v=0.

Optical and magnetic properties of the exact PPP states of biphenyl

The low-lying singlets and triplets of biphenyl are obtained exactly within the PPP model using the diagrammatic valence bond method. The energy gaps within the singlet manifold as well as the lowest singlet-triplet gap are found to be in good agreement with experimental results. The two weak absorptions between 4·1 and 4·2 eV reported experimentally are attributed to the two states lying below the optical gap that become weakly allowed on breaking electron-hole and inversion symmetries. The observed blue shift of the spectral lines, attributed to a change in dihedral angle, on going from crystalline to solution to vapour phase is also well reproduced within the PPP model. The bond orders show that the ground singlet state is benzenoidal while the dipole excited state as well as the lowest triplet state are quinonoidal and planar. Comparison with the experimental spin densities and the fine structure constants D and E in the triplet state point to slightly weaker correlations than assumed by the PPP model. The introduction of a 1-8 bond to mimic poly(paraphenylene)s gives an optical gap that is in good agreement with experiment.

Exact solution for the unsteady motion of a viscous-fluid in a porous annulus

An exact solution to the problem of time-dependent motion of a viscous fluid in an annulus with porous walls is obtained under the assumption that the rate of suction at one wall is equal to the rate of injection at the other. Finite Hankel transform is used to obtain a closed-form solution for the axial velocity. The average axial velocity profiles are depicted graphically.

S-matrix for magnons in the D1-D5 system

We show that integrability and symmetries of the near horizon geometry of the D1-D5 system determine the S-matrix for the scattering of magnons with polarizations in AdS(3) x S-3 completely up to a phase. Using semi-classical methods we evaluate the phase to the leading and to the one-loop approximation in the strong coupling expansion. We then show that the phase obeys the unitarity constraint implied by the crossing relations to the one-loop order. We also verify that the dispersion relation obeyed by these magnons is one-loop exact at strong coupling which is consistent with their BPS nature.

Exact traveling- wave solution for model geophysical systems

Exact traveling-wave solutions of time-dependent nonlinear inhomogeneous PDEs, describing several model systems in geophysical fluid dynamics, are found. The reduced nonlinear ODEs are treated as systems of linear algebraic equations in the derivatives. A variety of solutions are found, depending on the rank of the algebraic systems. The geophysical systems include acoustic gravity waves, inertial waves, and Rossby waves. The solutions describe waves which are, in general, either periodic or monoclinic. The present approach is compared with the earlier one due to Grundland (1974) for finding exact solutions of inhomogeneous systems of nonlinear PDEs.

Exact nonlinear travelling hydromagnetic wave solutions

Exact travelling wave solutions for hydromagnetic waves in an exponentially stratified incompressible medium are obtained. With the help of two integrals it becomes possible to reduce the system of seven nonlinear PDE's to a second order nonlinear ODE which describes an one dimensional harmonic oscillator with a nonlinear friction term. This equation is studied in detail in the phase plane. The travelling waves are periodic only when they propagate either horizontally or vertically. The reduced second order nonlinear differential equation describing the travelling waves in inhomogeneous conducting media has rather ubiquitous nature in that it also appears in other geophysical systems such as internal waves, Rossby waves and topographic Rossby waves in the ocean.

A note on resolving infeasibility in linear programs by constraint relaxation

We study the problem of finding a set of constraints of minimum cardinality which when relaxed in an infeasible linear program, make it feasible. We show the problem is NP-hard even when the constraint matrix is totally unimodular and prove polynomial-time solvability when the constraint matrix and the right-hand-side together form a totally unimodular matrix.

An Efficient Constraint Grammar Parser based on Inward Deterministic Automata

Pappret conceptualizes parsning med Constraint Grammar på ett nytt sätt som en process med två viktiga representationer. En representation innehåller lokala tvetydighet och den andra sammanfattar egenskaperna hos den lokala tvetydighet klasser. Båda representationer manipuleras med ren finite-state metoder, men deras samtrafik är en ad hoc -tillämpning av rationella potensserier. Den nya tolkningen av parsning systemet har flera praktiska fördelar, bland annat det inåt deterministiska sättet att beräkna, representera och räkna om alla potentiella tillämpningar av reglerna i meningen.

Algorithms for Exact Structure Discovery in Bayesian Networks

Bayesian networks are compact, flexible, and interpretable representations of a joint distribution. When the network structure is unknown but there are observational data at hand, one can try to learn the network structure. This is called structure discovery. This thesis contributes to two areas of structure discovery in Bayesian networks: space--time tradeoffs and learning ancestor relations. The fastest exact algorithms for structure discovery in Bayesian networks are based on dynamic programming and use excessive amounts of space. Motivated by the space usage, several schemes for trading space against time are presented. These schemes are presented in a general setting for a class of computational problems called permutation problems; structure discovery in Bayesian networks is seen as a challenging variant of the permutation problems. The main contribution in the area of the space--time tradeoffs is the partial order approach, in which the standard dynamic programming algorithm is extended to run over partial orders. In particular, a certain family of partial orders called parallel bucket orders is considered. A partial order scheme that provably yields an optimal space--time tradeoff within parallel bucket orders is presented. Also practical issues concerning parallel bucket orders are discussed. Learning ancestor relations, that is, directed paths between nodes, is motivated by the need for robust summaries of the network structures when there are unobserved nodes at work. Ancestor relations are nonmodular features and hence learning them is more difficult than modular features. A dynamic programming algorithm is presented for computing posterior probabilities of ancestor relations exactly. Empirical tests suggest that ancestor relations can be learned from observational data almost as accurately as arcs even in the presence of unobserved nodes.