Research and Advances

Thoth, a portable real-time operating system

Thoth is a real-time operating system which is designed to be portable over a large set of machines. It is currently running on two minicomputers with quite different architectures. Both the system and application programs which use it are written in a high-level language. Because the system is implemented by the same software on different hardware, it has the same interface to user programs. Hence, application programs which use Thoth are highly portable. Thoth encourages structuring programs as networks of communicating processes by providing efficient interprocess communication primitives.


Author Archives

Research and Advances

A fast method for solving a class of tridiagonal linear systems

The solution of linear systems having real, symmetric, diagonally dominant, tridiagonal coefficient matrices with constant diagonals is considered. It is proved that the diagonals of the LU decomposition of the coefficient matrix rapidly converge to full floating-point precision. It is also proved that the computed LU decomposition converges when floating-point arithmetic is used and that the limits of the LU diagonals using floating point are roughly within machine precision of the limits using real arithmetic. This fact is exploited to reduce the number of floating-point operations required to solve a linear system from 8n - 7 to 5n + 2k - 3, where k is much less than n, the order of the matrix. If the elements of the subdiagnals and superdiagonals are 1, then only 4n + 2k - 3 operations are needed. The entire LU decomposition takes k words of storage, and considerable savings in array subscripting are achieved. Upper and lower bounds on k are obtained in terms of the ratio of the coefficient matrix diagonal constants and parameters of the floating-point number system. Various generalizations of these results are discussed.
Research and Advances

On accurate floating-point summation

cumulation of floating-point sums is considered on a computer which performs t-digit base &bgr; floating-point addition with exponents in the range —m to M. An algorithm is given for accurately summing n t-digit floating-point numbers. Each of these n numbers is split into q parts, forming q·n t-digit floating-point numbers. Each of these is then added to the appropriate one of &eegr; auxiliary t-digit accumulators. Finally, the accumulators are added together to yield the computed sum. In all, q·n + &eegr; - 1 t-digit floating-point additions are performed. Let &ngr; = ⌈(M + m + 1)/(&eegr; + 1)⌉. If n ≤ (1/q)&bgr;⌈((q-1)/q)t⌈-&ngr;+1 (*), then the relative error in the computed sum is at most ⌈(t + 1)/&ngr;⌉&bgr;1-t. Further, with an additional q + &eegr; - 1 t-digit additions, the computed sum can be corrected to full t-digit accuracy. For example, for the IBM/360 (&bgr; = 16, t = 14, M = 63, m = 64), typical values for q and &eegr; are q = 2 and &eegr; = 32. In this case, (*) becomes n ≤ 1/2 × 164 = 32,768, and we have ⌈(t + 1)/&ngr;⌉&bgr;1-t = 4 × 16-13.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved