NON-LINEAR FUNCTIONS USING PIECEWISE POLYNOMIALS

AND METHODS OF USE

CROSS-REFERENCE TO RELATED APPLICATIONS This patent application claims the priority benefit of U.S. Patent Application No.

62/703,999 filed on July 27, 2018 for“Method for implementing piecewise polynomials in analog computing and application to non-linear function generation.” Further, this patent application hereby incorporates by reference U.S. Patent Application No. 62/703,999 for all purposes. Should any irreconcilable conflicts arise between this patent application and the teachings of U.S. Patent Application No. 62/703,999 for purposes of claim

construction/interpretation, then this patent application’s teachings shall govern.

BACKGROUND

Most computation in the present day is carried out by digital computers executing stored programs. Many whose lives are immersed in the world of digital computers are aware of analog computing only as a thing of historical interest— a way that people used to carry out computations before the replacement of analog computers by digital computers. What has, however, become clear in recent years is that there are some things even now that an analog computer can do better than a digital computer can do. And there are smart ways to permit a digital computer to work in concert with an analog computer, yielding what is sometimes termed“hybrid computing”.

This patent application directs itself to computation carried out by analog computers. It is important for the reader to appreciate that this patent application does not direct itself to digital simulation of analog computing. This patent application directs itself to physical analog computers which carry out computations in an analog way. In particular, this patent application directs itself to improvements in the design and function of physical analog computers.

The improved analog computers benefiting from the teachings of this patent application can then work in concert with digital computers to provide hybrid computing results that are better than previous hybrid computing results.

Some physical analog computers use voltages to represent the values being calculated. Other physical analog computers use currents to represent the values being calculated. With either approach, a number of building blocks make up the physical analog computer. For an analog computer that uses voltages to represent values, the typical building blocks include voltage sources, potentiometers (serving as voltage dividers), operational amplifiers configured as summers, and operational amplifiers configured as integrators. Other computing elements typically include analog multipliers, nonlinear function generators, and analog comparators.

Some discussion of what exactly a nonlinear function generator is may be helpful for some readers. In this context a nonlinear function generator is a physical circuit element having an analog electrical input (either a current or a voltage) that represents a numerical value, and having an analog electrical output (again, depending on the type of analog computer, the output might be a current or a voltage) which represents a numerical value. In a voltage-based analog computer, the input might for example be a voltage representing an angle and the output might be a voltage representing the sine of that angle. If so, then we would say that this function generator is a“sine” function generator.

This patent application particularly directs itself to an improved way to provide the physical computing element that is a nonlinear function generator.

Most applications of analog or hybrid computing (for example the task of solving a set of differential equations) require the evaluation of non-linear functions as part of the analog calculation. For example, sine or cosine functions might be required to solve a particular problem. Evaluating such functions on digital computers is a routine task;

however, on an analog computer it requires the development of a method to generate the values of such functions.

A common approach to deal with non-linear-function generation in analog computing is the continuous-time-table-lookup method. The implementation of such a method is presented in the publication N. Guo, Y. Huang, T. Mai, S. Patil, C. Cao, M. Seok, S.

Sethumadhavan, Y. Tsividis,“Energy-efficient hybrid analog/digital approximate computation in continuous time,” IEEE Journal of Solid-State Circuits 51 (7) (2016) 1514— 1524, as well as in U.S. Patent No. 5,006,850 (issued on April 9, 1991) to G.J. Murphy for “Function Transformer.” Disadvantages of the continuous-time-table-lookup method are:

• The continuous-time table lookup requires a storage medium, and analog-to- digital/digital-to-analog devices, and accordingly can result in excessive processing time and use of system resources; and

• The accuracy of the values generated by the continuous-time table lookup method depends on the size of the storage medium and the resolution of the analog-to-digital/digital- to-analog devices.

It should also be noted that the continuous-time-lookup-table method does not do any interpolating. Any value that is generated at the output of the function generator is simply the value based upon the information stored in the lookup table.

What is needed is a robust and efficient means for analog-computing systems to evaluate nonlinear functions. Given that adders and multipliers are commonly available building blocks in an analog computer, it would be helpful if some approach could be found that required the use only of adder and multiplier analog elements. It would be helpful if the approach could be flexible enough that it could be tailored to provide whatever degree of accuracy that is desired for the specific needs of a given application. BRIEF SUMMARY

The inventive disclosures described herein pertain to an implementation of a non- linear-function generator for hybrid computing. More generally, the implementation can be seen as a piecewise-polynomials evaluator for an analog computer. In embodiments, this piecewise-polynomials evaluator is coupled with interpolation techniques, such as cubic- spline interpolation, in order to efficiently implement non-linear-function generators in hybrid computers.

Compared to existing approaches, such as the use of continuous-time lookup tables, the improved method presents the following advantages:

• The accuracy of the non-linear-function generator is controllable by adjusting the degree (or order) of the spline interpolation scheme and the number of knots (as further discussed herein); and

• The implementation for evaluating piecewise polynomials in analog computers makes it possible to implement sophisticated and high-order interpolation schemes for high-accuracy. It should be noted that within the scope of the improved method a continuous-time lookup table can be seen as the zero-order implementation.

The foregoing Brief Summary is intended to merely provide a short, general overview of the inventive disclosure described throughout this patent application, and therefore, is not intended to limit the scope of the inventive disclosure contained throughout the balance of this patent application, including the appended claims and drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 depicts one spline interpolation example. The line denoted by triangles represents spline-interpolation results using cubic polynomials. The other line, denoted by squares, represents the original function. The solid black circles represent the knots used in the interpolation. This interpolation was obtained by using the second derivatives of the original function at the edge knots.

Figures 2A and 2B depicts one embodiment of a polynomial-evaluation

implementation diagram, with Figure 2A being an implementation diagram for Equations 11a, lib, and lie, infra , and with Figure 2B being an implementation of a cubic polynomial using three of the implementation blocks shown in Figure 2A.

Figure 3 shows a selector to be used for implementation of piecewise polynomials in analog computers. The input value X is the value at which the piecewise polynomial function is to be evaluated. The selector block receives the input value X and, based on the stored values of the nodes X,·, selects coefficients to be employed. The coefficients are used as inputs for the polynomial evaluator blocks.

Figure 4 shows the overall implementation of the piecewise polynomial evaluation.

DETAILED DESCRIPTION

Overview

Various applications of scientific computing and modeling rely on piecewise polynomial functions. Such functions are used, for example, in:

• finite-element methods to describe continuous quantities over discrete meshes; • various interpolation techniques to approximate functions, curves, or surfaces; and

• data analysis methods to fit mathematical models to data.

The inventive disclosures described herein pertain to an implementation of a non- linear-function generator for hybrid computing. More generally, the implementation can be seen as a piecewise-polynomials evaluator for an analog computer. In embodiments, this piecewise-polynomials evaluator is coupled with interpolation techniques, such as cubic- spline interpolation, in order to efficiently implement non-linear-function generators in hybrid computers.

As will be seen from the discussion that follows, compared to existing approaches, such as the use of continuous-time lookup tables, the improved method presents the following advantages:

• The accuracy of the non-linear-function generator is controllable by adjusting the degree (or order) of the spline interpolation scheme and the number of knots (as further discussed herein); and · The implementation for evaluating piecewise polynomials in analog computers makes it possible to implement sophisticated and high-order interpolation schemes for high-accuracy.

It should be noted that within the scope of the improved method a continuous-time lookup table can be seen as the zero-order implementation.

The term“analog computer,” as used in this specification, drawings, and any appended claims, refers to a type of computer that uses the continuously changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model a problem being solved. In contrast, digital computers represent varying quantities

symbolically, as their numerical values change. Because an analog computer does not use discrete values, but rather continuous values, processes cannot necessarily be reliably repeated with exact equivalence. However, unlike digital- signal processing in digital computers, analog computers do not suffer from the discrete error caused by quantization noise. Analog computers are subject to signal errors/perturbations from induced electronic noise. Analog computers and/or hybrid analog-digital computers (“hybrid computers”) are often used in scientific and industrial applications to perform control and protective functions. For the purposes of the disclosures contained herein, all references to“analog computers” are intended to also encompass“hybrid computers.”

An Improved Analog Computer Using Piecewise Polynomials to Evaluate Non- Linear Functions

This discussion is directed generally to an improved analog computer that features the ability to evaluate arbitrary non-linear functions in real-world applications using piecewise polynomials in real-world applications. Refer to Figures 1 through 4.

A. Overview of Mathematical Framework for Piecewise-Polvnomial Interpolation 1. Polynomial Definition A polynomial function P of a single variable X , denoted P(x), is a function defined as:

P : R R (Equation 1)

(Equation 2)

Where:

X is a real variable;

Ci is referred to as the coefficients of the polynomial P and

N is a positive integer (N= 0, 1, 2, . . . ) indexing the polynomial. We call N the“degree” of the polynomial.

This definition can easily be extended to multiple dimensions; however, for simplicity in this discussion, the scope is limited to one-dimensional polynomials.

Piecewise polynomials are defined by multiple polynomials, with each applying only to a specific interval. For example, consider the following definition: In other words, piecewise polynomials are simply a collection of polynomials, and depending on the variable value, a specific polynomial is evaluated.

2. Spline Interpolation

Spline interpolation is a powerful interpolation method based on piecewise polynomial functions. The following is a brief overview of the method for reference purposes:

Consider the case of a function f ( x ) defined over an interval [a, b] and assume that the values of this function at Appoints are available; that is, it is known that:

X _i , f (X _i ) ^º f _i for i = l, ... ,N (Equation 4) and these values are such that Xi ⁼ U and X _N ⁼ b. The values Xi are referred to as the nodes, and the values f ,· as the knots. The goal of an interpolation method is to provide an interpolant I(x) that reproduces the original function f up to some accuracy or within some error metric.

A spline interpolation solves this problem by defining N - 1 polynomial functions, each being defined in a range for the form [ ;, X; ₊ ], with / ⁼ 1 , . . . , /V - 1 These polynomials are denoted as Pi(x) these polynomials and we can then write the interpolant

It should be noted that the intervals in these definitions are conflicting when evaluated at the nodes. For example, when X ⁼ ₂ , both P _\ (x) and Pi(x) could be used. In practice (see below), this is not an issue as the interpolant is defined to be continuous at the nodes. In the previous example, this implies that .

Traditionally, the orders of the polynomials Pi(x) are all taken equal and this defines the order of the spline-interpolation scheme. That is, for a spline-interpolation scheme of order Q the polynomials are defined as:

(Equation 6)

Where:

i = 1, . .„ V - 1.

This defines a set of coefficients /— 1, . . . , TV- 1 and k— 0, . . . , Q that need to be calculated to define the interpolant. The number of coefficients tl _c is given by:

n _c =(Q + l)(iV— l) (Equation 7)

To define the interpolant, these coefficients need to be calculated and for a scheme of order Q , the following 2 (TV— 1) equations are first considered: (Equation 8a) (Equation 8b)

For interior nodes, / ⁼ 2, . . . , N 1, the following ( Q 1) (TV- 2) equations are used:

(Equation 9a)

i=2 ,. . . , N -1, (Equation 9b) j - 1, . . . , Q - 1. (Equation 9c)

The above expressions in Equations 9a - 9c correspond to the continuity of the first Q— 1 derivatives of the interpolant (these equations are defined for Q ³2 only). For a scheme of order 1 ( Q ⁼ 1), Equations 8a - 8b are sufficient to calculate all the coefficients of the interpolant (this leads to a well-defined linear system). For schemes of higher order,

Equations 8a - 8b and 9a - 9c, taken together, still leave Q 1 coefficients undetermined. This is handled in various ways depending on the order of the scheme:

• For quadratic scheme Q ⁼ 2, this is fixed by setting the first derivative of the interpolant at the first or last node (this can be set to zero or to the first derivative of the original function f ( x ). · For cubic scheme Q ⁼ 3, two additional equations are needed: o It is common to set the second derivatives of the interpolant to zero at both the first and last nodes (the so-called zero curvature scheme); and o Equally common is to use the second derivative values of the original

functions at both the first and last nodes.

o However, other choices exist, depending on the application.

Independently of these details, a spline-interpolation scheme boils down to solving a linear system of equations to determine the coefficients of the interpolant as defined in

Equation 5.

Figure 1 depicts an example of spline interpolation for the function

f (x )= cos (x) ³ exp (-0.2 x ) in the interval [-1, 4] The line denoted by triangles represents spline-interpolation results using cubic polynomials. The other line, denoted by squares, represents the original function. The solid black circles (six in total) represent the knots used in the interpolation. This interpolation was obtained by using the second derivatives of the original function at the edge knots.

B. Piecewise-Polynomials Evaluator for Analog Computing 1. Polynomial Evaluator

Consider a polynomial of degree (or order) Q written as: (Equation 10)

Implementing the computation of P( ^x ) in an analog computer using this straightforward formulation would require Q adders (for the overall summation) and Q(Q + l)/2 multipliers. For a cubic polynomial, this means three adders and six multipliers.

The same polynomial P (x ) can be expressed using the following recurrence relation:

(Equation 11a) (Equation lib)

P(x ) = G _i (x ) . (Equation 11c)

For a cubic polynomial, this recurrence relation is equivalent to the following formulation: (Equation 12)

The advantage of this formulation is that for a polynomial of degree (or order) Q , it requires Q adders and Q multipliers. In other words, the number of physical computational elements scales linearly with the degree (or order) of the polynomial.

The implementation of Equations 10a - 10c for an analog computer is shown in Figures 2A and 2B. Figure 2B also shows an example of implementation for a cubic polynomial. Within such an implementation the programming of the analog computer only requires the values of the polynomial coefficients.

2. Piecewise Polynomials in an Analog Computer

In light of the definition given in Equation 3, implementing piecewise polynomials in an analog computer requires the following:

A means of storing the coefficients for the various polynomials; and

A means of selecting the polynomial to be evaluated, depending on the input value X.

3. Selector Implementation

The selector implementation can be achieved in various ways. For example, previous works relied on memory storage and analog-to-digital converters (ADCs) to implement a continuous-time lookup table, as already discussed in the Background Section, supra.

Similar approaches could be used to store the nodes and polynomial coefficients values. However, such approaches cannot perform the selection based on intervals.

An embodiment of a general implementation is shown in Figure 3. The

implementation takes as input the value X for which the piecewise polynomial function p,(X) is to be evaluated. Based on the stored values of the nodes X _l (i ⁼ 1, , N ), the selector block can select the appropriate polynomial pi such that X, < X < X, + 1. The coefficients for the selected polynomials are then used as inputs for the polynomial evaluator blocks (shown in Figures 2A and 2B). The coefficients are drawn from memory storage and are provided to the polynomial evaluation system as coefficients c ₀ , ci, c ₂ , and C _3.

The overall implementation is shown in Figure 4. The coefficients c ₀ , Ci, c ₂ , and c ₃ selected by the selector are fed into the polynomial evaluator blocks. The blocks receive the input x. The output is the result which is the estimated value of the function being approximated.

4. Generalization beyond cubic polynomial scheme

The alert reader will appreciate on the one hand that, as suggested by Figure 1, a mere cubic polynomial approach can come remarkably close in approximating fairly complex nonlinear functions over relevant dynamic ranges. Depending upon the real-life problem that the analog computation attempts to solve, a mere cubic polynomial approach may well suffice for the goals of the computation.

Having said this, the alert reader will however further realize that if in a particular situation it were to develop that a cubic polynomial approach fails to come as close as is desired in approximating the nonlinear function of interest, it is quite workable to proceed to the use of higher-order polynomials. As mentioned above, everything about this invention scales more or less linearly. Yes one more polynomial evaluator block would be needed to increase the order of the polynomials by one. Yes the memory storage needs to store one more row or column of coefficients. The resources to be allocated expand linearly but not worse than linearly. C. Non-Linear-Function Generator

It is thus instructive to review an embodiment of an implementation for piecewise polynomials in analog computers can be leveraged to provide an efficient non-linear function generator for analog computers. In the case of an arbitrary function f ( x ) defined over some interval [a, b] In some variations, the following sequence of steps can be used to generate this function in an analog computer:

1. Select a spline-interpolation scheme by choosing a degree/order (e.g., a cubic spline with imposed second derivatives at the edge);

2. Select a number of nodes to span the interval [a, b],

3. Compute the coefficient of the spline polynomials; and

4. Program the analog computer selector element (as shown in Figure 3) with the node values and the spline polynomials coefficients.

In other words, it is sufficient to program the piecewise-polynomial evaluator from Figure 3 with the coefficients obtained by solving Equations 8a, 8b, 9a, 9b, and 9c. This provides a non-linear-function generator in the analog computer.

It should be noted that other forms of interpolation can be used. For example, if only the node values are stored within the analog computer, then it is still possible to implement an incremental quadratic interpolation as explained below. For an arbitrary function f ( x ), it is assumed we that the node values Xi have been selected such for any successive pair of nodes there is: f (xk + 1) - f (xk) = A ₉ (Equation 17)

Where: D is a fixed quantity.

When Xi < X < Xi + 1, the interpolant I(x) can be defined as:

I(c )=z D+ _< 5 (c) , (Equation 18) where the function <5(x) is a quadratic polynomial in the form: 5(c) = a x— x _.-2 +b [x-x _{i-2 l} , (Equation 19)

The two coefficients U and b can be solved by requiring that: (Equation 20a) d X _; =2D (Equation 20b) These equations uniquely define U and b and makes it possible to compute the interpolant value I(x).

The alert reader will have no difficulty devising myriad obvious variations and improvements to the invention, all of which are intended to be encompassed within the scope of the Description, Figures, and Claims herein.