We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points a₁,..., am ∈ Rn. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it has been the subject of much theoretical complexity analysis. Here we focus on computation. We present a combined interior-point and active-set method for solving this problem. Our computational results demonstrate that our method solves very large problem instances (m = 30,000 and n = 30) to a high degree of accuracy in under 30 seconds on a personal computer. / Singapore-MIT Alliance (SMA)

In passive target localization, source position is estimated by only using the source signal. In this thesis, position of a stationary target is estimated by using the data collected by a moving platform. Since the focus of the thesis is the location estimation, the parameters used for localization such as angle-of-arrival (AOA), time-difference-of-arrival (TDOA), Doppler frequency shift are assumed to be known. Different emitter localization methods are implemented in this thesis. Some of these methods are known in the literature and some are the modified or hybrid versions of these algorithms. Orthogonal Vector Estimator (OVE), Pseudolinear Estimator (PLE), Weighted Instrumental Variables Estimator (WIVE) and Maximum Likelihood Estimator (MLE) use only the AOA information. In MLE, Gauss Newton (GN) search algorithm is used to realize the search process effectively. AOA localization methods are also implemented together with the extended Kalman filter (EKF) realization. Doppler Shifted Frequency (DSF) based Least Squares (LS) and MLE are implemented which use Doppler frequency shift only. AOA-DSF combined hybrid algorithm is shown to perform better. LS and Maximum Likelihood (ML) TDOA localization methods are also implemented. AOA-DSF-TDOA combined hybrid algorithm is shown to perform better than the algorithms which use one type of parameter and AOA-DSF hybrid algorithm. Estimator performances are analyzed in this thesis. Error ellipsoid is a useful tool to evaluate an estimator

The main subject of this thesis is the development of new geometric tools and techniques for solving classic problems within the geometry of numbers and convex geometry. At a high level, the problems considered in this thesis concern the varied interplay between the continuous and the discrete, an important theme within computer science and operations research. The first subject we consider is the study of cutting planes for non-linear integer programs. Cutting planes have been implemented to great effect for linear integer programs, and so understanding their properties in more general settings is an important subject of study. As our contribution to this area, we show that Chvatal-Gomory closure of any compact convex set is a rational polytope. As a consequence, we resolve an open problem of Schrijver (Ann. Disc. Math. `80) regarding the same question for irrational polytopes. The second subject of study is that of ellipsoidal approximation of convex bodies. Different such notions have been important to the development of fundamental geometric algorithms: e.g. the ellipsoid method for convex optimization (enclosing ellipsoids), or random walk methods for volume estimation (inertial ellipsoids). Here we consider the construction of an ellipsoid with good "covering" properties with respect to a convex body, known in convex geometry as the M-ellipsoid. As our contribution, we give two algorithms for constructing M-ellipsoids, and provide an application to near-optimal deterministic volume estimation in the oracle model. Equipped with this new geometric tool, we move to the study of classic lattice problems in the geometry of numbers, namely the Shortest (SVP) and Closest Vector Problems (CVP). Here we use M-ellipsoid coverings, combined with an algorithm of Micciancio and Voulgaris for CVP in the ℓ₂ norm (STOC `10), to obtain the first deterministic 2^O(ⁿ) time algorithm for the SVP in general norms. Combining this algorithm with a novel lattice sparsification technique, we derive the first deterministic 2^O(ⁿ)(1+1/ϵ)ⁿ time algorithm for (1+ϵ)-approximate CVP in general norms. For the next subject of study, we analyze the geometry of general integer programs. A central structural result in this area is Kinchine's flatness theorem, which states that every lattice free convex body has integer width bounded by a function of dimension. As our contribution, we build on the work Banaszczyk, using tools from lattice based cryptography, to give a new and tighter proof of the flatness theorem. Lastly, combining all the above techniques, we consider the study of algorithms for the Integer Programming Problem (IP). As our main contribution, we give a new 2^O(ⁿ)nⁿ time algorithm for IP, which yields the fastest currently known algorithm for IP and improves on the classic works of Lenstra (MOR `83) and Kannan (MOR `87).

In this study, a double-ellipsoid structure is proposed for measurements of optical properties of liquid-crystal displays (LCDs). By using the double-ellipsoid structure, light dispersion and measurement time, which occurs during the measurement of optical properties of LCDs, can be greatly reduced. The system also significantly decreases reflective loss on interface, increasing the accuracy of the measurement. Moreover, by using the conoscopy measured from the proposed structure, light distribution of the dark state along off-axis direction can be analyzed. Based on the analysis, the cell gap and pretilt angle of vertical alignment liquid-crystals (VA-LCs) are evaluated. The proposed structure, which exhibits a fast and high accuracy measurement, is highly promising for future optical measurement of LCDs.

abstract: Proportional-Integral-Derivative (PID) controllers are a versatile category of controllers that are commonly used in the industry as control systems due to the ease of their implementation and low cost. One problem that continues to intrigue control designers is the matter of finding a good combination of the three parameters - P, I and D of these controllers so that system stability and optimum performance is achieved. Also, a certain amount of robustness to the process is expected from the PID controllers. In the past, many different methods for tuning PID parameters have been developed. Some notable techniques are the Ziegler-Nichols, Cohen-Coon, Astrom methods etc. For all these techniques, a simple limitation remained with the fact that for a particular system, there can be only one set of tuned parameters; i.e. there are no degrees of freedom involved to readjust the parameters for a given system to achieve, for instance, higher bandwidth. Another limitation in most cases is where a controller is designed in continuous time then converted into discrete-time for computer implementation. The drawback of this method is that some robustness due to phase and gain margin is lost in the process. In this work a method of tuning PID controllers using a loop-shaping approach has been developed where the bandwidth of the system can be chosen within an acceptable range. The loop-shaping is done against a Glover-McFarlane type ℋ∞ controller which is widely accepted as a robust control design method. The numerical computations are carried out entirely in discrete-time so there is no loss of robustness due to conversion and approximations near Nyquist frequencies. Some extra degrees of freedom owing to choice of bandwidth and capability of choosing loop-shapes are also involved and are discussed in detail. Finally, comparisons of this method against existing techniques for tuning PID controllers both in continuous and in discrete-time are shown. The results tell us that our design performs well for loop-shapes that are achievable through a PID controller. / Dissertation/Thesis / M.S. Electrical Engineering 2011

We will consider the scenario of the co-rotation of a fluid star (in specific, a neutron star) and a black hole. The neutron star (or primary)is assumed to have constant angular velocity. The tidal effects on the primary are investigated. First, the centrally condensed approximation is applied, where both bodies are considered as point sources. In the second treatment, the primary is treated as an incompressible and homogeneous fluid mass, which in addition to its own gravity is subject to centrifugal and Coriolis forces, derived from fluid motions. The black hole (or secondary) is treated as a rigid sphere and can be regarded as a point mass. The equilibrium figure is derived. The problem is then adapted to include vorticity and a pseudo-Newtonian potential. The coalescence of neutron star - black hole binaries and their importance to gravitational wave detection is also discussed. / Mathematical Sciences / M. Sc. (Applied Mathematics)

京都大学 / 0048 / 新制・課程博士 / 博士(医学) / 甲第20996号 / 医博第4342号 / 新制||医||1027(附属図書館) / 京都大学大学院医学研究科医学専攻 / (主査)教授 鈴木 茂彦, 教授 富樫 かおり, 教授 開 祐司 / 学位規則第4条第1項該当 / Doctor of Medical Science / Kyoto University / DFAM

The skin friction and cross-flow separation location on a non-body-of-revolution (non-BOR) ellipsoidal model performing constant-yaw turns and a pitch-up maneuver, each with roll oscillation were studied for the first time. The detailed, low uncertainty, flow topology data provide an extensive experimental database on the flow over non-BOR hull shapes that does not exist anywhere else in the world and serves as a crucial tool for computational validation. The ellipsoidal model was mounted on a roll oscillation machine in the Virginia Tech Stability Wind Tunnel slotted wall test section. Hot-film sensors with constant temperature anemometers provided skin friction magnitudes on the body's surface for thirty-three steady flow model orientations and three unsteady maneuvers at a constant Reynolds number of 2.5 million. Cross-flow separation locations on the model were determined from span-wise minima in the skin friction magnitude for both the steady orientations and unsteady maneuvers. Steady hot-film data were obtained over roll angles between ±25° in 5° increments with the model mounted at 10° and 15° yaw and at 7° pitch with respect to the flow. The roll oscillation machine was used to create a near sinusoidal unsteady roll motion between ±26° at a rate of 3 Hz, which corresponded to a non-dimensional roll period of 5.4. Unsteady data were obtained with the ellipsoidal model mounted at 10° and 15° yaw and at 7° pitch during the rolling maneuver. Cross-flow separation was found to dominate the leeside flow of the model for all orientations. For the yaw cases, the separation location moved progressively more windward and inboard as the flow traveled downstream. Increasing the model roll or yaw angle increased the adverse pressure gradient on the leeward side, creating stronger cross-flow separation that began further upstream and migrated further windward on the model surface. For the pitch flow case, the cross-flow separation remained straight as the flow moved axially downstream. The strongest pitch cross-flow separation was observed at the most negative roll angle and dissipated, moving further downstream and inboard as the model's roll angle was increased. The unsteady flow maneuvers exhibited the same flow topology observed in the quasi-steady conditions. However, the unsteady skin friction and separation locations lagged their quasi-steady counterparts at equivalent roll angles during the oscillation cycle. A first order time lag model and sinusoidal fit to the separation location data quantified the time lags that were observed. / Ph. D.

Nous présentons une série d’expériences sur des particules micrométriques de polystyrène de formes ellipsoïdales. Les rapports d’aspects (k) des particules sont variables, de 0.2 à 8 environ. Ces ellipsoïdes sont manipulés dans l’eau par faisceau laser modérément focalisé. On observe la lévitation et l’équilibre dynamique de chaque particule, dans le volume et au contact d’une interface, solide-liquide ou liquide-liquide. Dans une première partie, nous montrons que des particules de k modéré sont piégées radialement. Par contre, les ellipsoïdes allongés (k>3) ou aplatis (k<0.3) ne peuvent pas être immobilisés. Ces particules « dansent » autour du faisceau, dans un mouvement permanent associant translation et rotation. Les mouvements sont périodiques, ou irréguliers (chaotiques) selon les caractéristiques de la particule et du faisceau. Un modèle en 2d est proposé qui permet de comprendre l’origine des oscillations. La seconde partie est une application de la lévitation optique pour une étude de la transition mouillage total-mouillage partiel des particules à l’interface eau-air. Nous montrons que la dynamique de la transition ne dépend pratiquement pas de la forme de particule, et qu’elle est déterminée par le mécanisme d’accrochage-décrochage de la ligne de contact. / We report experiments on ellipsoidal micrometre-sized polystyrene particles. The particle aspect ratio (k) varies between about 0.2 and 8. These particles are manipulated in water by means of a moderately focused laser beam. We observe the levitation and the dynamical state of each particle in the laser beam, in bulk water or in contact to an interface (water-glass, water-air, water-oil). In the first part, we show that moderate-k particles are radially trapped with their long axis lying parallel to the beam. Conversely, elongated (k>3) or flattened (k<0.3) ellipsoids never come to rest, and permanently “dance” around the beam, through coupled translation-rotation motions. The dynamics are periodic or irregular (akin to chaos) depending on the particle type and beam characteristics. We propose a 2d model that indeed predicts the bifurcation between static and oscillating states. In the second part, we apply optical levitation to study the transition from total to partial wetting of the particles at the water-air interface. We show that the dynamics of the transition is about independent of particle shape, and mainly governed by the pinning-depinning mechanism of the contact line.

本文證明對∂－方程式在橢圓域中的解皆可用積分形式表現出來而且滿足均勻估計。在此估計中的常數可用橢圓的長短軸表達之。而且，我們也證明了此常數具有穩定性。 / In this thesis, we prove that, given any smooth closed (0,1)-form f near an ellipsoid Ω in Cⁿ, the Henkin's solution H_Ωf of the ∂-equation on Ω satisfies the uniform estimate 　　　　║H_Ωf║_∞≦C_Ω║f║_∞　　， 　　where is the Henkin's constant of Ω which can be explicitly estimated in terms of the maximum and minimum axes of the ellipsoid Ω. Also, a special version of the stability result of the Henkin's constant C_Ω is obtained.