No description available.

No description available.

This thesis investigates the computation of piecewise polynomial solutions to ill- conditioned linear systems of equations when noise on the linear measurements is observed. Specifically, we enhance our understanding of and provide qualifications on when such ill-conditioned systems of equations can be solved to a satisfactory accuracy. We show that the conventional condition number of the coefficient matrix is not sufficiently informative in this regard and propose a more relevant conditioning measure that takes into account the decay rate of singular values. We also discuss interactions of several factors affecting the solvability of such systems, including the number of discontinuities in solutions, as well as the distribution of nonzero entries in sparse matrices. In addition, we construct and test an approach for computing piecewise polynomial solutions of highly ill-conditioned linear systems using a randomized, SVD-based truncation, and L1-norm regularization. The randomized truncation is a stabilization technique that helps reduce the cost of the traditional SVD truncation for large and severely ill-conditioned matrices. For L1-minimization, we apply a solver based on the Alternating Direction Method. Numerical results are presented to compare our approach that is faster and can solve larger problems, called RTL1 (randomized truncation L1-minimization), with a well-known solver PP-TSVD.

Lookup-table (LUT)-based method is a common approach used in all kinds of research topics. In this dissertation, we present several new designs for table-based function evaluation and table-based error correcting coding. In Chapter 3, a new function evaluation method, called two-level approximation, is presented where piecewise degree-one polynomials are used for initial approximation in the first level, followed by the refined approximation for the shared normalized difference functions in the second level. In Chapter 4, we present a new non-uniform segmentation method that searches for the optimal segmentation scheme with the different design goals of minimizing either ROM, total area, or delay. In Chapter 5, a new design methodology for table-based function evaluation is presented. Unlike previous approaches that usually determine the bit widths by assigning allowable errors for individual hardware components, the total error budget of our new design is considered jointly in order to optimized the bit widths of all the hardware components, leading to significant improvements in both area and delay. Finally, in Chapter 6, the similar table-based concept is used in the design of error correcting encoder using the modified polynomial of the Lagrange interpolation formula, resulting in smaller critical path delay and lower power consumption.

Function evaluation is often used in many science and engineering applications. In order to reduce the computation time, different hardware implementations have been proposed to accelerate the speed of function evaluation. Table-based piecewise polynomial approximation is one of the major methods used in hardware function evaluation designs that require simple hardware components to achieve desired precision. Piecewise polynomial method approximates the original function values in each partitioned subinterval using low-degree polynomials with coefficients stored in look-up tables. Errors are introduced in the hardware implementations. Conventional error analysis in piecewise polynomial methods includes four types of error sources: polynomial approximation error, coefficient quantization error, arithmetic truncation error, and final rounding error. Typical design approach is to pre-allocated maximum allowable error budget for each individual hardware component so that the total error induced from these individual errors satisfies the bit accuracy. In this thesis, we present a new design approach by jointly considering the error sources in designing all the hardware components, including look-up tables and arithmetic units, so that the total area cost is reduced compared to the previously published designs.

Splines are piecewise polynomial functions of a given order of smoothness r on a triangulated region (or polyhedrally subdivided region) of Rd. The set of splines of degree at most k forms a vector space Crk() Moreover, a nice way to study Cr k()is to embed n Rd+1, and form the cone b of with the origin. It turns out that the set of splines on b is a graded module Cr b() over the polynomial ring R[x1; : : : ; xd+1], and the dimension of Cr k() is the dimension o This dissertation follows the works of Billera and Rose, as well as Schenck and Stillman, who each approached the study of splines from the viewpoint of homological and commutative algebra. They both defined chain complexes of modules such that Cr(b) appeared as the top homology module. First, we analyze the effects of gluing planar simplicial complexes. Suppose 1, 2, and = 1 [ 2 are all planar simplicial complexes which triangulate pseudomanifolds. When 1 \ 2 is also a planar simplicial complex, we use the Mayer-Vietoris sequence to obtain a natural relationship between the spline modules Cr(b), Cr (c1), Cr(c2), and Cr( \ 1 \ 2). Next, given a simplicial complex , we study splines which also vanish on the boundary of. The set of all such splines is denoted by Cr(b). In this case, we will discover a formula relating the Hilbert polynomials of Cr(cb) and Cr (b). Finally, we consider splines which are defined on a polygonally subdivided region of the plane. By adding only edges to to form a simplicial subdivision , we will be able to find bounds for the dimensions of the vector spaces Cr k() for k 0. In particular, these bounds will be given in terms of the dimensions of the vector spaces Cr k() and geometrical data of both and . This dissertation concludes with some thoughts on future research questions and an appendix describing the Macaulay2 package SplineCode, which allows the study of the Hilbert polynomials of the spline modules.

在迴歸分析中，若變數間具有非線性 (nonlinear) 的關係時，B-Spline線性迴歸是以無母數的方式建立模型。B-Spline函數為具有節點(knots)的分段多項式，選取合適節點的位置對B-Spline函數的估計有重要的影響，在希望得到B-Spline較好的估計量的同時，我們也想要只用少數的節點就達成想要的成效，於是Huang (2013) 提出了一種選擇節點的方式APLS (Adaptive penalized least squares)，在本文中，我們以此方法進行一些更一般化的設定，並在不同的設定之下，判斷是否有較好的估計效果，且已修正後的方法與基於BIC (Bayesian information criterion)的節點估計方式進行比較，在本文中我們將一般化設定的APLS法稱為GAPLS，並且經由模擬結果我們發現此兩種以B-Spline進行迴歸函數近似的方法其近似效果都很不錯，只是節點的個數略有不同，所以若是對節點選取的個數有嚴格要求要取較少的節點的話，我們建議使用基於BIC的節點估計方式，除此之外GAPLS法也是不錯的選擇。 / In regression analysis, if the relationship between the response variable and the explanatory variables is nonlinear, B-splines can be used to model the nonlinear relationship. Knot selection is crucial in B-spline regression. Huang (2013) propose a method for adaptive estimation, where knots are selected based on penalized least squares. This method is abbreviated as APLS (adaptive penalized least squares) in this thesis. In this thesis, a more general version of APLS is proposed, which is abbreviated as GAPLS (generalized APLS). Simulation studies are carried out to compare the estimation performance between GAPLS and a knot selection method based on BIC (Bayesian information criterion). The simulation results show that both methods perform well and fewer knots are selected using the BIC approach than using GAPLS.