Numerical Algorithms Group |
 |
|
The K system for GLMs in Genstat NAG Ltd, Oxford, February 1993 The K system provides a compact command language for generalised linear modelling in Genstat and has been designed to be especially suitable for intensive interactive work. It is similar in structure to the GLIM language.
Accurate Singular Values and Differential qd Algorithms NAG Limited, Oxford, July 1992 We have discovered a new implementation of the qd algorithm that has a far wider domain of stability than Rutishauser's version. Our algorithm was developed from an examination of the LR-Cholesky transformation and can be adapted to parallel computation in stark contrast to traditional qd. Our algorithm also yields useful a posteriori upper and lower bounds on the smallest singular value of a bidiagonal matrix. The zero-shift bidiagonal QR of Demmel and Kahan computes the smallest singular values to maximal relative accuracy and the others to maximal absolute accuracy with little or no degradation in efficiency when compared with the LINPACK code. Our algorithm obtains maximal relative accuracy for all the singular values and runs at least four times faster than the LINPACK code. BRANKIN, L.A. and MUMFORD, A.M. File Forms for Computer Graphics Unraveling the Confusion NAG Limited, Oxford, June 1992. HODGSON, G.S. Rationale for the Proposed Standard for Packages of Real and Complex Type Declarations and Basic Operations for Ada (including Vector and Matrix Types) NAG Limited, Oxford, May 1991 This paper supplements the Proposed Standard for Packages of Real and Complex Type Declarations and Basic Operations for Ada (including Vector and Matrix Types), to be submitted by the ISO-IEC/JCT1/SC22/WG9 (Ada) Numerics Rapporteur Group. Based on recommendations made jointly by the Ada-Europe Numerics Working Group and the ACM SIGAda Numerics Working Group, the proposed real and complex vector and matrix standard is the third of several anticipated secondary standards to address the interrelated issues of portability, efficiency and robustness of numerical software written in Ada. Its purpose, features and development are outlined in this commentary. ACM SIGADA and ADA-EUROPE NUMERICS WORKING GROUPS Proposed Standard for Packages of Real and Complex Type Declarations and Basic Operations for Ada (including Vector and Matrix Types) DONGARRA, J.J., MAYES, P.J.D and RADICATI DI BROZOLO, G. The IBM RISC System/6000 and Linear Algebra Operations NAG Limited, Oxford, January 1991 This paper discusses the IBM RISC System/6000 workstation and a set of experiments with blocked algorithms commonly used in solving problems in numerical linear algebra. We describe the performance of these algorithms and discuss the techniques used in achieving high performance on such an architecture. DATARDINA, S., DU CROZ, J.J., HAMMARLING, S.J. and PONT, M.W. A Proposed Specification of BLAS Routines in C NAG Limited, Oxford, January 1991 This report proposes specifications for a set of C equivalents to the Fortran specifications for the Basic Linear Algebra Subprograms (BLAS). DU CROZ, J.J. and HAMMARLING, S.J. Parallelism and the NAG Library NAG Limited, Oxford, December 1990 This report describes NAG's evolving approach to the adaptation and development of the NAG Library for modern high-performance computers. Much of the report concentrates on the Fortran version of the NAG Library, but we make reference to other important work as well. We discuss our achievements and aims over the last ten or so years and discuss recent and current projects concerned with future developments in the NAG Library. The situation as at the date of the report is described and we expect to update this report in the future as significant developments take place. SLICOT Library, Release 1 WGS, Eindhoven/NAG Limited, Oxford, September 1990 This report describes the software and documentation standards that have been used to produce the first release of the SLICOT Library. It was produced in collaboration with the Benelux Working Group on Software (WGS), and contains guidelines for potential contributors to the Library. This report is being issued jointly as Numerical Algorithms Group Publication NP2032 and Working Group on Software WGS-Report 90-1. LIPINKSI, T. The TIE2 System NAG Limited, Oxford, January 1990 HAGUE, S.J. ESPRIT II Project : 2620 FOCUS - First Annual Report, Summary of Progress, 31 January 1990 NAG Limited, Oxford, February 1990 This report describes the work undertaken during the first year of the ESPRIT II project number 2620 - FOCUS (Front-Ends for Open and Closed User Systems) which started in December 1988 and is planned to last for four years. In this report, we state the aims of the FOCUS project, describe the strands of investigation, list the project participants, and summarize the current state of progress and the main highlights of the work programme for the second year of the project. DU CROZ, J.J. and MAYES, P.J.D. NAG Fortran Library Vectorization Review NAG Limited, Oxford, December 1989 This report reviews the work that has been done over the last six years to improve the performance of the NAG Fortran Library Routines on vector-processing machines. It is presented in two parts, each based on an article in the NAG Newsletter (issues 1/89 and 2/89). Part 1 covers linear algebra. Part 2 covers random number generation, quadrature and FFTs (with applications to PDEs) FERNANDO, K.V. and PARLETT, B.N. Stable Column-Oriented Algorithms for the SVD and Spectral Factorizations NAG Limited, Oxford, in preparation. FERNANDO, K.V. and PONT, M.W. Computing Accurate Eigenvalues of a Hermitian Matrix NAG Limited, Oxford, December 1989 This paper describes an algorithm to compute the eigenvalues and eigenvectors of a Hermitian matrix, with guaranteed intervals containing the eigenvalues, and gives the specification of an Ada implementation of the algorithm. The approach presented in this paper incorporates a Jacobi method to compute a good initial approximation to the eigensolution. Newton iterations are then used to improve the eigenvalues and eigenvectors. Such improved eigenvalues are accurate to the basic machine precision. Please note that a version of this report appeared in: Accurate Numerical Algorithms (Ch. Ullrich and J. Wolff von Gudenberg, eds.) Springer-Verlag, pp. 104-115, 1989. DU CROZ, J.J., ERL, M., GARDNER, P.P., HODGSON, G.S. and PONT, M.W. Validation of Numerical Computations in Ada NAG Limited, Oxford, May 1989 An Ada Extended FPV package has been developed for the validation of commonly-used arithmetic operators, including the fundamental arithmetic operators. It can be used to check an already existing implementation or during the development phase of a new system. By validation we mean an experimental verification that a floating-point arithmetic has been correctly implemented according to its specification. The user describes this specification in terms of parameters - base, precision, exponent range, and rounding rule; FPV then attempts to verify that the arithmetic conforms to those parameters by probing for errors in a systematic and rigorous fashion. It does not attempt to judge the efficiency of the implementation. Most implementations can satisfy the tests performed by Ada Extended FPV if the criteria for acceptance are suitably relaxed; only the better implementations satisfy the most stringent criteria. Ada Extended FPV is a substantial generalisation of the concepts of previous versions in Fortran and Pascal. The Ada system consists of a generic package which can be instantiated by a user with appropriate types, objects and subprograms to be tested. The package generates its own test operands, applies its internal simulation of the tested operator to the operands, applies the tested operator itself to the operands, and compares the results. The package copes with testing both the model arithmetic (defined by the Ada language) and the underlying machine arithmetic. BRANKIN, R.W. and GLADWELL, I. Codes for Almost Block Diagonal Systems NAG Limited, Oxford, February 1989 We present a new set of codes for solving almost block diagonal systems of linear equations and for performing multiplicative operations with matrices represented using the same data structures. These data structures arise when solving ordinary differential equation boundary value problems with non-separated boundary conditions by finite differences, and when using spline collocation methods. Our codes are written in a modular form using the BLAS and are intended to take advantage of vector architecture and, to a limited extent, parallelism. FERNANDO, K.V. On Ultimate Quadratic Convergence of Jacobi Methods NAG Limited, Oxford, December 1988 Two of the important mathematical objects in quadratic convergence analysis are the asymptotic error constant and the radius of convergence. In this report we derive the radii of convergence for the row cyclic, the general cyclic and the classical Jacobi methods based on worst case analysis. Our asymptotic error constants for the two cyclic and the general cyclic methods are sharper than that given by the results of Wilkinson. TR15/88 (NP1843) (Combined with TR14/88; Replaces TR12/87) DONGARRA, J.J., DU CROZ, J.J., HAMMARLING, S.J. and DUFF, I.A Set of Level 3 Basic Linear Algebra Subprograms: Model Implementation and Test Programs Argonne National Laboratory/NAG Limited, Oxford/Harwell Laboratory, August 1988 This paper describes a model implementation and test software for the Level 3 Basic Linear Algebra Subprograms (Level 3 BLAS). The Level 3 BLAS are targeted at matrix-vector operations with the aim of providing more efficient, but portable, implementations of algorithms on high-performance computers. The model implementation provides a portable set of Fortran 77 Level 3 BLAS for machines where specialised implementations do not exist or are not required. The test software aims to verify that specialised implementations meet the specification of the Level 3 BLAS and that implementations are correctly installed. Please note that a version of TR15/88 appeared in: ACM Trans. Math. Softw., 16, pp. 1-28, 1990. TR14/88 (NP1842) (Combined with TR15/88; Replaces TR12/87) DONGARRA, J.J., DU CROZ, J.J., HAMMARLING, S.J. and DUFF, I.A Set of Level 3 Basic Linear Algebra Subprograms Argonne National Laboratory/NAG Limited, Oxford/Harwell Laboratory, August 1988 This paper describes a set of Level 3 Basic Linear Algebra Subprograms (Level 3 BLAS). The Level 3 BLAS are targeted at matrix-matrix operations with the aim of providing more efficient, but portable, implementations of algorithms on high-performance computers, especially those with hierarchical memory and parallel processing capability. Please note that a version of TR14/88 appeared in: ACM Trans. Math. Softw., 16, pp. 1-28, 1990. O'BRIEN, C.M. The GLIMPSE System NAG Limited, Oxford, September 1988 O'BRIEN, C.M. Working with GLIMPSE - Modelling the Formation of Calcium Oxalate Crystals in Urine NAG Limited, Oxford, September 1988 O'BRIEN, C.M. Working with GLIMPSE - Modelling the Cost of Construction of Nuclear Power Plants NAG Limited, Oxford, September 1988 O'BRIEN, C.M. Working with GLIMPSE - Estimated Determination of the Composition of a Chemical Specimen (activation analysis) NAG Limited, Oxford, September 1988 O'BRIEN, C.M. Working with GLIMPSE - Modelling the Survival of Breast Cancer Patients Following Radical Mastectomy NAG Limited, Oxford, September 1988 TR5A/88 (NP1821) (Replaces TR6/86, TR6A/86, TR18/87 and TR5/88) FERNANDO, K.V.Linear Convergence of the Row Cyclic Jacobi and Kogbetliantz Methods NAG Limited, Oxford, August 1988 Linear convergence of the row cyclic Jacobi and Kogbetliantz methods can be guaranteed if certain constraints concerning the angles of rotations are implemented. Unlike the results of Forsythe and Henrici, convergence can be achieved without under-rotations. Please note that a version of this report appeared in: Numerische Mathematik, 56, pp. 73-91, 1989. MAYES, P.J.D. Block Factorisation Algorithms on the IBM 3090/VF NAG Limited, Oxford, August 1988 This report describes a series of experiments performed with block versions of theLU , Cholesky andQR factorisations using Level 3 BLAS on the IBM 3090/VF. FERNANDO, K.V., HAMMARLING, S.J. Parallel Eigenvalue and Singular Value Algorithms for Signal Processing NAG Limited, Oxford, September 1988 Please note that a version of this report appeared in: Aspects of Computation on Asynchronous Parallel Processors (M. Wright, ed.) North Holland, Amsterdam, pp. 13-22, 1989. TR4A/88 (NP1778) (Replaces TR11/87 and TR4/88) FERNANDO K.V.Stability of 2D State-Space Systems NAG Limited, Oxford, October 1988 A method is proposed for the verification of stability of 2D state-space systems. Unlike previous tests, this requires only a finite number of mathematical steps to determine stability. Please note that a version of this report appeared in: Applications of Matrix Theory (M.J.C. Gover and S. Barnett, eds.) Oxford University Press, Oxford, pp. 171-192, 1989. TR2/88 (NP1674) (Replaces TR6/87 and TR6A/87) FERNANDO K.V. and HAMMARLING S.J.Unified Mesh-connected Architecture for Eigenvalue, Singular Value and QR decompositions NAG Limited, Oxford, March 1988 The square systolic array proposed by Stewart for computation of the Schur decomposition of a matrix requires 1/2n**2 + O(n) number of processors while Luk's triangular systolic array for computation of the singular value decomposition is composed of 1/4n**2 + O(n) processor elements. Both these methods are based on the same odd-even ordering of annihilations. We propose modified arrays where the number of processors are reduced by a factor of four asymptotically by exploiting the redundancies in the architecture of Stewart. This architecture is also suitable for the QR decomposition. Furthermore, it is not necessary to have a separate data array independent of the processor array as the elements of the matrix can be assigned to local memories of the processors. The proposed arrays can be described as mesh-connected architectures. FERNANDO, K.V. and HAMMARLING, S.J. On Block Kogbetliantz Methods for Computation of the SVD NAG Limited, Oxford, December 1987 The notions of inner and outer rotations are crucial in the development of convergent Jacobi and Kogbetliantz methods. We extend these concepts to the block case and indicate how to implement several block Kogebetliantz methods. Please note that a version of this report appeared in: SVD and Signal Processing - Algorithms, Applications and Architectures, (F. Deprettere, ed.) North Holland, Amsterdam, pp. 349-355, 1988 CARPENTER, L.A. Portable Graphical Software Design, Implementation and Use NAG Limited, Oxford, July 1987 Please note that a version of this report appeared in: Computer Physics Communications, 50, pp. 159-168, 1988 FERNANDO, K.V. On Equivalence and Convergence of Jacobi and Kogbetliantz Methods with Odd-even Orderings NAG Limited, Oxford, January 1988 The results concerning equivalence between the classical row cyclic and the odd-even methods derived by Schwiegelshohn and Thiele and the extensions by Luk and Park are incomplete. We show that equivalence relationships, in the sense of Hansen, can be derived provided further conditions are met. The proof of convergence of odd-even methods given by Luk and Park also contains certain deficiencies due to the use of the conditions of Forsythe and Henrici which require under-rotations for convergence. We implement convergent odd-even algorithms by mapping convergent row cyclic methods of Fernando which do not require under-rotations via the derived equivalences. We also realise convergent odd-even algorithms in the Luk triangular systolic array. BERZINS, M., BRANKIN, R.W. and GLADWELL, I. Design of the Stiff Integrators in the NAG Library University of Leeds/NAG Limited, Oxford/University of Manchester, July 1987. This paper describes the design philosophy behind the recent replacement of the NAG Ordinary Differential Equation (ODE) stiff integrators. This replacement is intended to update the ODE chapter algorithmically but, more importantly in the context of this paper, it provides a more flexible interface than has been available in the past. This interface is designed to permit a wide variety of problem and method definitions, to provide flexibility when introducing new methods or problem definitions in the future and to allow straightforward use of the software as the integrator in packages implementing, for example, the method of lines for parabolic partial differential equations. BRANKIN, R.W., DORMAND, J.R., GLADWELL, I., PRINCE, P.J. and SEWARD, W.L. A Runge-Kutta-Nystrom Code NAG Limited, Oxford/Teesside Polytechnic/University of Manchester/Oxford University, July 1987 A robust, reliable, efficient code implementing recently-developed Runge-Kutta-Nystrom (RKN) formulas is described. The methods used are two embedded formula pairs with an interpolation feature associated with the lower order pair. The structure of the code is based on a modular approach to the design of software for the numerical solution of ordinary differential equations. The documentation for the code is included with an example driver program in an Appendix. FERNANDO, K.V. The Kalman Reachability/Observability Canonical Form and the SVD NAG Limited, Oxford, July 1987 The Kalman reachability/observability canonical form is one of the most fundamental decompositions available for linear systems. We show that the Product Induced Singular Value Decomposition (SVD) of Fernando and Hammarling is a powerful tool for obtaining the Kalman form. It is well known that this canonical form can be obtained via a similarity transformation. In this report, we prove that it can be derived via an orthogonal transformation given by they SVD. This indicates that numerically stable algorithms can be designed for computing the Kalman form and solving related problems since orthogonal transformations are numerically well conditioned. TR8/87 (NP1474) (Replaces TR1/87) FERNANDO, K.V. and HAMMARLING, S.J.A Product Induced Singular Value Decomposition (PISVD) for Two Matrices and Balanced Realisation NAG Limited, Oxford, May 1987 A new decomposition PISVD for two matrices A and B, induced by the singular value decomposition of the matrix product AB**T is proposed which complements the generalized singular value decomposition (GSVD) of Paige and Saunders. It has the structure A = U[GammaRQ**T 0]W**T, B = V[DeltaS**T Q**T 0]W**T, S = R**-1 where U, V, W and Q are orthogonal, Gamma and Delta are quasi-diagonal and R and S are nonsingular triangular.Since (A**TA)(B**TB) = [ (QR**T)(Gamma**T Gamma Delta**T Delta)(QR**T)**-10] W [ ] W**T [0 0] is an eigenvalue decomposition, the proposed decomposition is also a canonical form for the product of two symmetric non-negative definite matrices. It is possible to compute this decomposition using a Kogbetliantz method which can also be implemented in a systolic array. Application of this decomposition in balanced (principal axis) realisation of linear systems is highlighted. Please note that a version of this report appeared in: Linear Algebra in Signals, Systems and Control, (B.N. Datta, C.R. Johnson, M.A. Kaashoek, R.J. Plemmons and E.D. Sontag, eds.). SIAM, Philadelphia, PA, April 1988. BRANKIN, R.W. and GLADWELL, I. Using Shape Preserving Local Interpolation for Plotting Solutions of Ordinary Differential Equations NAG Limited, Oxford/University of Manchester, January 1987 We study the piecewise rational interpolants of Delbourgo and Gregory in an important application. It is shown how the interpolants may be employed to preserve shape and produce a visually pleasing approximiation to the solution of ordinary differential equations (ODE's). Results of numerical experiments are given to show how the rational interpolants compare to using cubic Hermite interpolation in this context. Also, bounds are derived which enable efficient plotting of the rational interpolants. TR4/87 (NP1418) (Combined with TR3/87; Replaces TR3/86) DONGARRA, J.J., DU CROZ, J.J., HAMMARLING, S.J. and HANSON, R.J.An Extended Set of Basic Linear Algebra Subprograms: Model Implementation and Test Programs NAG Limited, Oxford/Argonne National Laboratory/Sandia National Laboratory Albuquerque, February 1987 This paper describes a model implementation and test software for the Level 2 Basic Linear Algebra Subprograms (Level 2 BLAS). The Level 2 BLAS are targeted at matrix-vector operations with the aim of providing more efficient, but portable, implementations of algorithms on high-performance computers. The model implementation provides a portable set of Fortran 77 Level 2 BLAS for machines where specialised implementations do not exist or are not required. The test software aims to verify that specialised implementations meet the specification of the Level 2 BLAS and that implementations are correctly installed. TR3/87 (NP1417) (Combined with TR4/87; Replaces TR3/86) DONGARRA, J.J., DU CROZ, J.J., HAMMARLING, S.J. and HANSON, R.J.An Extended Set of Fortran Basic Linear Algebra Subprograms NAG Limited, Oxford/Argonne National Laboratory/ Sandia National Laboratory Albuquerque, February 1987 This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extensions are targeted at matrix-vector operations which should provide for efficient and portable implementations of algorithms for high-performance computers. Please note that a version of TR4/87 and TR3/87 appeared in: ACM Trans. Math. Softw., 14, pp. 1-32, 1988. FERNANDO, K.V. Quadratic Convergence of the Cyclic Kogbetliantz Method for Triangular Matrices NAG Limited, Oxford, January 1987 The quadratic rate of convergence derived by Paige and Van Dooren for the cyclic Kogbetliantz method for computing the SVD can be improved if the matrix is assumed to be triangular instead of being rectangular. This report follows more closely the analysis of Wilkinson for the Jacobi method than that of Paige and Van Dooren. FERNANDO, K.V. and HAMMARLING, S.J. Kogbetliantz Methods for Parallel SVD Computation: Architecture, Algorithms and Convergence NAG Limited, Oxford, November 1986 Computation of the singular value decomposition via Kogbetliantz methods is essentially based on the solution of a series of SVD problems involving 2 by 2 matrices, some of which can be concurrently computed. Thus this approach is ideally suited for VLSI machines such as systolic arrays, hypercubes, and other ensemble architectures. A sufficient condition for convergence of Kogbetliantz methods is derived which is based on the angles of rotations but which is independent of the topology of the architecture. As particular examples, we look at the square systolic array of Brent et al. and the triangular systolic array of Luk and show that they satisfy the sufficient condition for convergence. We also formulate the cyclic method in this framework. GLADWELL, I. Vectorisation of One-Dimensional Quadrature Codes NAG Limited, Oxford/University of Manchester, December 1986 We investigate certain vectorisation aspects of one-dimensional quadrature codes. For purposes of illustration we use the NAG code D01AKF (corresponding to the QUADPACK code QAG-6). This is an adaptive integration code using 61-point Gauss Kronrod quadrature with a 31-point rule for error estimation. We aim to use little or no more arithmetic than in D01AKF and to obtain an improvement on scalar machines as well as on vector processors. We close with an outline algorithm suitable for multiprocessors which has a similar philosophy. FERNANDO, K.V. and HAMMARLING, S.J. Systolic Array Computation of the SVD of Complex Matrices NAG Limited, Oxford, September 1986 Algorithms of reduced complexity are developed for the computation of SVD of complex matrices in the triangular systolic array of Luk. A sufficient condition of convergence of these algorithms is also given which is similar to the real matrix problem. Please note that a version of this report appeared in: Proc. SPIE, (Advanced Algorithms and Architectures for Signal Processing), 696, pp. 54-61, 1986. FERNANDO, K.V. VLSI Computation of the SVD of Real Matrices via the Method of Kogbetliantz Part 1: Algorithms for Diagonalisation of 2 by 2 Real Matrices. NAG Limited, Oxford, March 1986 Algorithms for diagonalisation of 2 by 2 real matrices using orthonormal transformations are developed which are paramount in VLSI computation of the singular value decomposition based on the method of Kogbetliantz. HURLEY, S. Computation of the Singular Value Decomposition Using Systolic Arrays NAG Limited, Oxford, March 1986 We present an overview of the computation of the singular value decomposition of a general m by n (m>=n) real matrix, using systolic array type architectures. A brief description of systolic arrays is also presented. HAMMARLING, S.J. The Numerical Solution of the Kalman Filtering Problem NAG Limited, Oxford, October 1985 We present a short historical perspective of the numerical solution of the Kalman filtering problem covering 25 years from the Kalman paper of 1960. Please note that a version of this report appeared in: Computational and Combinatorial Methods in Systems Theory, (C.I. Byrnes and A. Lindquist, eds.). North Holland, Amsterdam, pp. 23-36, 1986. HAMMARLING, S.J. The Numerical Solution of the General Gauss-Markov Linear Model NAG Limited, Oxford, October 1985 We present an overview of the numerical solution of the linear least-squares problem associated with the general Gauss-Markov linear model y = XBeta + e, e is a product of sets N(0,sigma**2 W), where sigma**2 W is a symmetric non-negative definite variance-covariance matrix. Please note that a version of this report appeared in: Mathematics in Signal Processing (T.S. Durrani, J.B. Abbiss, J.E. Hudson, R.N. Madan, J.G. McWhirter and T.A. Moore, eds.), Clarendon Press, Oxford, pp. 441-456, 1987. FERNANDO, K.V. Conditions for Internal Stability of 2D Systems NAG Limited, Oxford, October 1985 The numerical range (the field value) of a matrix is generalised for two matrices and via this extension new stability conditions for 2D systems are derived. Please note that a version of this report appeared in: Systems and Control Letters, 7, pp. 183-187, 1986. |
© Numerical Algorithms Group
Visit NAG on the web at:
www.nag.co.uk (Europe and ROW)
www.nag.com (North America)
www.nag-j.co.jp (Japan)
http://www.nag.co.uk/doc/techrep/TRarchive.asp