Error-free polynomial matrix computations
著者
書誌事項
Error-free polynomial matrix computations
(Texts and monographs in computer science)
Springer-Verlag, c1985
大学図書館所蔵 全20件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
注記
Companion vol. to: Methods and applications of error-free computation / R.T. Gregory, E.V. Krishnarmurthy. c1984
Bibliography: p. [146]-150
Includes index
内容説明・目次
内容説明
This book is written as an introduction to polynomial matrix computa- tions. It is a companion volume to an earlier book on Methods and Applications of Error-Free Computation by R. T. Gregory and myself, published by Springer-Verlag, New York, 1984. This book is intended for seniors and graduate students in computer and system sciences, and mathematics, and for researchers in the fields of computer science, numerical analysis, systems theory, and computer algebra. Chapter I introduces the basic concepts of abstract algebra, including power series and polynomials. This chapter is essentially meant for bridging the gap between the abstract algebra and polynomial matrix computations. Chapter II is concerned with the evaluation and interpolation of polynomials. The use of these techniques for exact inversion of poly- nomial matrices is explained in the light of currently available error-free computation methods. In Chapter III, the principles and practice of Fourier evaluation and interpolation are described. In particular, the application of error-free discrete Fourier transforms for polynomial matrix computations is consi- dered.
目次
I Algebraic Concepts.- 1 Introduction.- 2 Groups, Rings, Integral Domains, and Fields.- 2.1 Groups.- 2.2 Rings.- 2.3 Integral domain.- 2.4 Unique factorization domain.- 2.5 Euclidean domains.- 2.6 Field F.- 2.7 Use of EEA to compute multiplicative inverse.- 2.8 Additional properties of EEA.- 2.9 Ideals, principal ideals, quotient rings.- 3 Power Series and Polynomials.- 3.1 Formal power series R[[x]].- 3.2 Polynomial rings.- 3.3 Field of quotients.- 3.4 Examples.- 3.5 Division property of F[x].- 3.6 Examples.- 3.7 Congruence properties.- 4 Chinese Remainder Theorem and Interpolation.- 4.1 Chinese remainder theorem.- 4.2 Theorem.- 4.3 Equivalence to Lagrange interpolation.- 4.4 Algorithm for reconstructing r and r(x).- 4.5 Residue representation of signed integers.- 5 Polynomials in Several Variables.- 5.1 Definition.- 5.2 Formal power series.- 5.3 Pseudodivision and remainder theorem.- 5.4 Evaluation-interpolation.- Exercises I.- II Polynomial Matrix-Evaluation, Interpolation, Inversion.- 1 Introduction.- 2 Results from Matrix Theory.- 2.1 Matrices over fields.- 2.2 Matrices over F[x].- 2.3 Elementary transformations.- 2.4 Smith Canonical form.- 2.5 Substitution.- 2.6 Inverse matrix.- 3 Matrix Method-Evaluation and Interpolation of Single Variable Polynomials.- 3.1 Single variable polynomial matrix inversion.- 3.2 Modular method.- 4 Tensor Product Method-Evaluation and Interpolation of Multi-variable Polynomials.- 4.1 Two-dimensional grid evaluation-interpolation.- 4.2 Tensor products and their properties.- 4.3 Use of tensor product for grid evaluation-interpolation.- 4.4 Inversion of multivariable polynomial matrices.- Exercises II.- III Fourier Evaluation and Interpolation.- 1 Introduction.- 2 Discrete Fourier Transform over a Ring.- 2.1 Primitive nth root of unity.- 2.2 Discrete Fourier transform (DFT).- 2.3 Theorem.- 2.4 Inverse discrete Fourier transform (IDFT).- 3 Convolution.- 3.1 Cyclic convolution property (CCP).- 3.2 Remarks.- 4 Error-Free DFT.- 4.1 Basic number theoretic results.- 4.2 Number theoretic transforms (NTT).- 4.3 Mersenne transforms.- 4.4 Fermat and Rader transforms.- 5 Polynomial Evaluation-Interpolation-Multiplication.- 5.1 Single-variable polynomial multiplication.- 5.2 Example.- 5.3 Choice of modulus for computation.- 5.4 Example.- 5.5 Complexity reduction.- 6 Multivariable Polynomial Interpolation.- 6.1 Example.- 6.2 Choice of resulting vector length and coefficient size.- 6.3 Example.- 6.4 Complexity reduction.- 6.5 Example.- Exercises III.- IV Polynomial Hensel Codes.- 1 Introduction.- 2 Hensel Fields.- 2.1 Hensel's lemma.- 2.2 Bibliographic remarks.- 3 Isomorphic Algebras.- 3.1 Similar algebras.- 3.2 Morphism.- 3.3 Bibliographic remarks.- 3.4 Hensel Codes for rational numbers.- 4 Hensel Codes for Rational Polynomials.- 4.1 Definitions and notation.- 4.2 Forward mapping.- 4.3 Theorem.- 4.4 Theorem.- 4.5 Theorem (Uniqueness of Coding).- 4.6 Hensel Codes.- 4.7 Forward mapping.- 4.8 Inverse mapping.- 5 Arithmetic of Hensel Codes.- 5.1 Complementation/negation.- 5.2 Addition/subtraction.- 5.3 Multiplication.- 5.4 Multiplicative inverse and division.- 5.5 Newton-Hensel-Zassenhaus (NHZ) iterative method.- 5.6 Euclidean algorithm for finding H(p, r, ?(x)-1).- 6 Forward and Inverse Mapping Algorithms.- 6.1 Forward mapping.- 6.2 Inverse mapping-Pade method.- 6.3 Euclidean inverse mapping.- 6.4 Common denominator method.- 7 Direct Solution of Linear Systems and Matrix Inversion.- 7.1 Gaussian elimination (with scaling).- 7.2 Matrix inversion using reduction.- 7.3 Generalized inverses.- 7.4 Generalized inverse by evaluation-interpolation.- 8 Hensel-Newton-Schultz Iterative Matrix Inversion.- 8.1 Theorem.- 8.2 Example.- 8.3 Inversion of matrices in ?(x).- 8.4 Generalized inversion by iteration.- 8.5 Recursive property.- 8.6 Relation to diophantine approximation.- Exercises IV.- V Matrix Computations-Euclidean and Non-Euclidean Domains.- 1 Introduction.- 2 Matrices over Euclidean Domains.- 2.1 Matrices over I.- 2.2 Matrices over R[x].- 3 Matrices over Non-Euclidean Domains.- 4 Multivariable Polynomial Hensel Codes.- 4.1 Hensel Codes.- 4.2 Forward mapping.- 4.3 Inverse mapping.- 4.4 Arithmetic.- 4.5 Inversion of multivariable polynomial matrix-Gaussian elimination.- 4.6 Iterative inversion of a multivariable polynomial matrix.- 4.7 Iterative g-inversion.- Exercises V.
「Nielsen BookData」 より