Browse Prior Art Database

Fast Hybrid Solution of Algebraic Systems

IP.com Disclosure Number: IPCOM000037167D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 6 page(s) / 91K

Publishing Venue

IBM

Related People

Douglas, CC: AUTHOR [+3]

Abstract

A fast equation solver consisting of both analog and digital circuitry is proposed. This hybrid combination is expected to give better results than digital techniques alone. The basic idea is to use an analog solver as a preconditioner for a digital iterative process. Thus, both high speed from a fast exchange of information in analog circuitry and high precision from digital circuitry can be obtained. Eventually, both types of circuits should be integrated onto a single chip. (Image Omitted)

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 37% of the total text.

Page 1 of 6

Fast Hybrid Solution of Algebraic Systems

A fast equation solver consisting of both analog and digital circuitry is proposed. This hybrid combination is expected to give better results than digital techniques alone. The basic idea is to use an analog solver as a preconditioner for a digital iterative process. Thus, both high speed from a fast exchange of information in analog circuitry and high precision from digital circuitry can be obtained. Eventually, both types of circuits should be integrated onto a single chip.

(Image Omitted)

The applicability of the method is essentially limited by the requirement ek << 1, where e is the relative precision of the analog circuitry and k is the condition number of the linear system. For the multilevel solver, the condition number involved is the one for the linear system on the coarsest level. The time required for the analog part of the method also depends on the condition number. This time is negligible in comparison to that for the digital part of the method when ek << 1.

The principal benefits of the proposed method will manifest themselves with advancements in technology: analog circuitry has the potential to avoid the information exchange bottleneck of massively parallel digital computation. Essentially, a trade of arithmetic precision for fast dissemination of information between the processors is being made.

These techniques will be advantageous for large but moderately conditioned positive definite problems with well-defined nonzero structures. Systems arising by either finite element or finite difference discretizations of partial differential equation problems are one area of application. For a general non-sparse system, the number of connections required is prohibitive.

The defect correction approach to the hybrid method is new and offers, as yet, unexplored possibilities in massive parallel computations.

The precision of contemporary analog circuitry is up to 10 bits [1] using capacitors as basic circuit components. Optical processors have the same or lower precision 2. A purely optical analog method for solving linear systems was presented in 3. See 4 for a survey of basic concepts of optical computing.

Consider a system of linear equations in matrix notations:

Ax* = f, (1) where A is an nxn nonsingular matrix and x* is the exact solution.

Sometimes, the hypothesis that A is symmetric, positive definite will be assumed. In the following algorithm, a standard residual correction technique is used to solve the system, except that part of the computation is performed digitally and part is performed with an analog solver. Hybrid Algorithm {

1

Page 2 of 6

H1. For given x1 ,compute r = f - Ax1 digitally.

H2. Convert the n components of r into n parallel

analog

signals. Using an analog solver, solve the

equation

Ay = r.

Convert the n components of y (in parallel) to

digital output.

H3. Compute x2 = x1 + y digitally.

H4. Set x1 = x2 and go to step H1.

}

See Fig. 1.

Assume that the pre...