We study numerical stability for interior-point methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. <br /><br /> We start with the error bound analysis of the search directions for the normal equation approach for LP. Our error analysis explains the surprising fact that the ill-conditioning is not a significant problem for the normal equation system. We also explain why most of the popular LP solvers have a default stop tolerance of only 10^-8 when the machine precision on a 32-bit computer is approximately 10^-16. <br /><br /> We then propose a simple alternative approach for the normal equation based interior-point method. This approach has better numerical stability than the normal equation based method. Although, our approach is not competitive in terms of CPU time for the NETLIB problem set, we do obtain higher accuracy. In addition, we obtain significantly smaller CPU times compared to the normal equation based direct solver, when we solve well-conditioned, huge, and sparse problems by using our iterative based linear solver. Additional techniques discussed are: crossover; purification step; and no backtracking. <br /><br /> Finally, we present an algorithm to construct SDP problem instances with prescribed strict complementarity gaps. We then introduce two <em>measures of strict complementarity gaps</em>. We empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the strict complementarity gaps correlate well with the number of iteration for the SDPT3 solver, as well as with the local asymptotic convergence rate; and (iii) large strict complementarity gaps, coupled with the failure of Slater's condition, correlate well with loss of accuracy in the solutions. In addition, the numerical tests show that there is no correlation between the strict complementarity gaps and the geometrical measure used in [31], or with Renegar's condition number.

We study numerical stability for interior-point methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. <br /><br /> We start with the error bound analysis of the search directions for the normal equation approach for LP. Our error analysis explains the surprising fact that the ill-conditioning is not a significant problem for the normal equation system. We also explain why most of the popular LP solvers have a default stop tolerance of only 10^-8 when the machine precision on a 32-bit computer is approximately 10^-16. <br /><br /> We then propose a simple alternative approach for the normal equation based interior-point method. This approach has better numerical stability than the normal equation based method. Although, our approach is not competitive in terms of CPU time for the NETLIB problem set, we do obtain higher accuracy. In addition, we obtain significantly smaller CPU times compared to the normal equation based direct solver, when we solve well-conditioned, huge, and sparse problems by using our iterative based linear solver. Additional techniques discussed are: crossover; purification step; and no backtracking. <br /><br /> Finally, we present an algorithm to construct SDP problem instances with prescribed strict complementarity gaps. We then introduce two <em>measures of strict complementarity gaps</em>. We empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the strict complementarity gaps correlate well with the number of iteration for the SDPT3 solver, as well as with the local asymptotic convergence rate; and (iii) large strict complementarity gaps, coupled with the failure of Slater's condition, correlate well with loss of accuracy in the solutions. In addition, the numerical tests show that there is no correlation between the strict complementarity gaps and the geometrical measure used in [31], or with Renegar's condition number.

As the current electronic trend is toward integrating multiple functions in a single electronic device, there is a clear need for increasing integration density which is becoming more emphasized than in the past. To meet the industrial need and realize the new system-integration law [1], three-dimensional (3-D) integration is becoming necessary. 3-D integration of multiple functional IC chip/package modules requires co-simulation of the chip and the package to evaluate the performance of the system accurately. Due to large scale differences in the physical dimensions of chip-package structures, the chip-package co-simulation in time-domain using the conventional FDTD scheme is challenging because of Courant-Friedrich-Levy (CFL) condition that limits the time step. Laguerre-FDTD has been proposed to overcome the limitations on the time step. To enhance performance and applicability, SLeEC methodology [2] has been proposed based on the Laguerre-FDTD method. However, the SLeEC method still has limitations to solve practical 3-D integration problems. This dissertation proposes further improvements of the Laguerre-FDTD and SLeEC method to address practical problems in 3-D interconnects and 3-D integration. A method that increases the accuracy in the conversion of the solutions from Laguerre-domain to time-domain is demonstrated. A methodology that enables the Laguerre-FDTD simulation for any length of time, which was challenging in prior work, is proposed. Therefore, the analysis of the low-frequency response can be performed from the time-domain simulation for a long time period. An efficient method to analyze frequency-domain response using time-domain simulations is introduced. Finally, to model practical structures, it is crucial to model dispersive materials. A Laguerre-FDTD formulation for frequency-dependent dispersive materials is derived in this dissertation and has been implemented.