JP5317429B2 - Eigen equation solver, solver program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To eliminate a square root calculation, to reduce a division, and to find a proper solution. <P>SOLUTION: This solution device or the like is provided with an initial value generating circuit 42 having a divider 45 for dividing a coefficient in a second order term of a cubic equation by "3" constituting a denominator of the solution, as to the solution of an equation with a second-differential cubic eigenvalue equation of a 3&times;3 determinant, a first group block 43 having two circuits 50<SB>1</SB>, 50<SB>2</SB>of dichotomy circuits for finding one solution, using a dichotomy, based on two initial values, and of using an output from the initial value generating circuit 42, zero and a MAX value that is a sum of the maximum values of diagonal elements in the 3&times;3 determinant, as inputs for the dichotomy circuits, and a block of the second group block 44 having three circuits 50<SB>3</SB>, 50<SB>4</SB>, 50<SB>5</SB>of dichotomy circuits using zero and the MAX value and an output from the first group block 43, as inputs. <P>COPYRIGHT: (C)2009,JPO&amp;INPIT

Description

The present invention, solving apparatus applicable eigenequation in various fields for performing processing using the eigenvalue calculation, it relates to solving program.

Conventionally, when solving an Nth-order eigen equation used when calculating eigenvalues, many divisions and square root calculations are performed, and an error propagates due to an increase in the number of cycles, and an eigenvalue with poor accuracy is output. There was a problem. In addition, there are problems such as an increase in the number of areas of elements that perform division and square root calculation, and a longer development period when performing semiconductor design.

  As an apparatus for analyzing a nonlinear equation by performing iterative calculation, there is a device described in Patent Document 1, which sets a convergence judgment condition to speed up the analysis, but eliminates the square root calculation and performs division. It is not an invention from the viewpoint of reducing the above.

JP 2003-162517 A

The present invention has been made in view of the current state of the conventional apparatus for solving eigen equations as described above, and the object thereof is to eliminate the square root calculation and reduce the division. can be obtained, it is possible to reduce the reduction and error propagation in the number of elements, in the case of an LSI is solving device eigenvalue equation which can shorten the development time, provides a solving program That is.

Solving device characteristic equations according to the present invention, the characteristic equation of the next coefficient is an integer each element configured N-th square matrices by the number represented by the binary number (N-1) order derivative to The obtained linear equation solution is expressed in the form of an irreducible fraction with the number of constant terms of the linear equation minus the number and the coefficient of the primary term of the linear equation as the denominator. The dividing means for dividing the coefficient of the (N-1) th order term of the Nth order equation by the number constituting the denominator of the solution and / or the first order equation when N is a multiple of 2. An initial value generating circuit having shift means for shifting the coefficient to the right in correspondence with the exponent of 2 obtained when the denominator of the solution is factorized and expressed in a form using an exponent ; and two initial values There are two dichotomy circuits for finding one solution based on the dichotomy. , The output of the initial value generating circuit, a first group blocks the MAX value is the sum of the maximum value which can be taken each diagonal elements at zero and the N-th square matrices and the input of the dichotomy circuit, the binary Blocks having up to (N-1) th group having 3, 4,..., (N-1) circuit, each of which receives the MAX value, zero and the output of the previous group block as inputs. It is characterized by comprising.

In the eigen equation solving apparatus according to the present invention, the bisection circuit calculates, for the two input values, an intermediate value calculating means for determining an intermediate value that is a midpoint value of two points corresponding to these values, and the intermediate value is calculated. First function value calculating means for obtaining a function value as a variable in the function of the corresponding degree equation, and a function value as a variable in the function of the corresponding degree equation using one of the two input values or the previous intermediate value as a variable. Based on the sign of the function value obtained by the second function value calculating means and the first and second function value calculating means, one of the values used for the previous intermediate value calculation is selected to calculate the intermediate value. And a numerical value supply control means for supplying the intermediate value calculated to the intermediate value calculating means together with the intermediate value calculated by the means.

An apparatus for solving an eigen equation according to the present invention is an N-order bisection method for obtaining N solutions of an eigen equation of an N-order square matrix using a bisection method, and a function in the N-order equation F (X) = 0. The minimum value and the maximum value of F (X) are obtained by a (N-1) degree equation which is a derivative of the Nth order equation. The (N-1) degree bisection method means, the (N-1) degree equation F '( (N-2) a bisection method for degree (N-2) which obtains a minimum value and a maximum value of a function F ′ (X) at X) = 0 by a (N-2) degree equation which is a derivative of the (N-1) degree equation; ..., a quadratic bisection method for obtaining a minimum value and a maximum value of the function f (X) in the cubic equation f (X) = 0 by a quadratic equation that is a derivative of the cubic equation; create a solution of linear equations is a differential equation, Noso diagonal elements in this solution and the zero and the N-th square matrices Initial value giving means for giving a MAX value that is the sum of the maximum values that can be taken to the secondary bisection means, the N-order bisection means, and the (N-1) secondary bisection method. Means,... Execute processing with the output of the preceding means, zero, and the MAX value as inputs.

The eigen-equation solving apparatus according to the present invention includes an N-order bisection method, an (N-1) -order bisection method,..., A bisection of N, (N-1),. It comprises a modulo operation means, and each dichotomy operation means obtains one solution using a dichotomy based on two initial values.

In the eigen equation solving apparatus according to the present invention, the bisection method calculating means obtains an intermediate value that is a midpoint value of two points corresponding to these values for the two input values , and the intermediate value And a first function value calculating means for obtaining a function value as a variable in the function of the corresponding degree equation, and a function value as a variable in the function of the corresponding degree equation by using one of the two input values or the previous intermediate value as a variable. Based on the second function value calculation means and the sign of the function value obtained by the first and second function value calculation means, one of the values used for the previous intermediate value calculation is selected, and the intermediate value is selected. And a numerical value supply control means for supplying the intermediate value calculated by the calculating means to the intermediate value calculating means.

A program for solving an eigen equation according to the present invention is an Nth-order bisection means for obtaining N solutions of an eigen equation of an N-order square matrix by using a bisection method, the N-order equation F (X) = The (N-1) degree bisection means for obtaining the minimum value and the maximum value of the function F (X) at 0 by the (N-1) degree equation which is a derivative of the Nth order equation, the (N-1) degree equation The minimum value and the maximum value of the function F ′ (X) at F ′ (X) = 0 are determined by the (N−2) degree equation which is a derivative of the above (N−1) degree equation. A quadratic bisection method for obtaining a minimum value and a maximum value of the function f (X) in the cubic equation f (X) = 0 by a quadratic equation that is a derivative of the cubic equation; A solution of a linear equation that is a derivative of the quadratic equation is created, and this solution, zero, and the Nth order square Functioning as an initial value giving means for giving a MAX value, which is the sum of the maximum values that can be taken by each of the diagonal elements in the sequence, to the secondary bisection means, and the N-order bisection means, (N-1) The second dichotomy means,... Controls to execute the process with the output from the preceding means, zero, and the MAX value as inputs.

Solving program characteristic equations according to the present invention, N following a dichotomy means, (N-1) following a dichotomy means, ... are respectively, N pieces, (N-1) pieces, bisecting ... It comprises a modulo operation means, and each dichotomy operation means obtains one solution using a dichotomy based on two initial values.

In the eigen equation solving program according to the present invention, the bisection calculation means obtains an intermediate value that is an intermediate value between two points corresponding to these values for the two input values , and the intermediate value. And a first function value calculating means for obtaining a function value as a variable in the function of the corresponding degree equation, and a function value as a variable in the function of the corresponding degree equation by using one of the two input values or the previous intermediate value as a variable. Based on the second function value calculation means and the sign of the function value obtained by the first and second function value calculation means, one of the values used for the previous intermediate value calculation is selected, and the intermediate value is selected. And a numerical value supply control means for supplying the intermediate value calculated by the calculating means to the intermediate value calculating means.

According to the present invention, a linear equation obtained by differentiating an eigen equation of an N-order square matrix in which each order coefficient is an integer and each element is constituted by a number represented by a binary number (N-1) times. When the solution of is expressed in the form of an irreducible fraction with the number obtained by adding a minus to the number of constant terms of the linear equation as the numerator and the coefficient of the primary term of the linear equation as the denominator, An initial value generating circuit for giving an initial value to the modulus circuit divides the coefficient of the (N-1) th order term of the Nth order equation by the number constituting the denominator of the solution and / or N is a multiple of 2 Since the denominator of the solution of the linear equation in the case of ## EQU1 ## is composed of shift means for shifting the coefficient to the right in correspondence with the exponent for 2 obtained when prime factorization is used and expressed in a form using an exponent . Square root operation is eliminated, division is reduced, and the number of elements is reduced. In each stage, since the dichotomy is performed using the solution obtained in the previous stage, error propagation is blocked at each stage, and error propagation is blocked by repeating square root calculation, division, etc. Therefore, the error propagation can be reduced as compared with the conventional method for obtaining a final solution without any problem, and in the case of LSI, the development period can be shortened.

  Further, according to the present invention, since the structure uses a plurality of bisection circuits having the same configuration, the circuit can be shared and the development period can be shortened.

Furthermore, the present invention adopts a configuration in which the minimum value and the maximum value are obtained and sent to the bisection method in the next stage, and in addition to the minimum value and the maximum value, each of the diagonal elements in the zero and Nth order square matrices is adopted. Since the solution value is obtained by the bisection method with the MAX value that is the sum of the maximum values obtained as an initial value, processing by the dichotomy method is performed based on the two values sandwiching the solution, and the solution can be obtained appropriately.

DESCRIPTION OF EMBODIMENTS Hereinafter, embodiments of an eigen equation solving apparatus and an solving program according to the present invention will be described with reference to the accompanying drawings. In each figure, the same components are denoted by the same reference numerals and redundant description is omitted. As shown in FIG. 1, the eigen-equation solving apparatus according to the present embodiment is generally an N-order bisection method for obtaining N solutions of an N-th order eigen equation by an N-order square matrix by using a bisection method. 10 _N.

Also it comprises (N-1) following a dichotomy means _{10 (N-1),} · · ·, 2-order for dichotomy means 10 _2. (N-1) degree bisection means 10 _(N-1) is a derivative of the above-mentioned Nth order equation for the minimum and maximum values of the function F (X) in the Nth order equation F (X) = 0 (N -1) It is obtained by the following equation. (N-2) Next bisection method 10 _(N-2) calculates the minimum value and the maximum value of the function F ′ (X) in the above-mentioned (N−1) -order equation F ′ (X) = 0. -1) It is obtained by a (N-2) linear equation which is a derivative of the linear equation. Thereafter, the same means are provided according to N, as the leading stage, the secondary use dichotomy means 10 ₂ is provided, the secondary for dichotomy means 10 _2, processing in the dichotomy means comprising a subsequent stage The minimum value and the maximum value of the function f (X) in the cubic equation f (X) = 0 related to the object are obtained by the quadratic equation f ′ (X) = 0 which is a derivative of the cubic equation f (X) = 0. Is.

Further, the solution finding apparatus is provided with an initial value giving means 11. The initial value applying means 11 is given coefficient value of N next equation and from the equation generating unit 13 for generating a characteristic equation based on the elements of a given N-th square matrices, of the secondary for dichotomy means 10 _of processing A solution of a linear equation that is a derivative of a quadratic equation related to the object is created, and a MAX value (hereinafter simply referred to as a sum of the maximum value that can be taken by each of the zero elements and the diagonal elements in the N-order square matrix is created. the) that MAX value is intended to be given to the secondary for dichotomy means 10 _2. As a result, with respect to the secondary use dichotomy means 10 _2, zero and MAX values are given with the solution of the equation is a minimum value in a function of the quadratic equation are given as an initial value. The initial value assigning means 11 retains a numerical value that is not included in the coefficient of the original Nth-order equation and becomes a differential coefficient, and uses this as the Nth-order bisection means 10 _N , (N−1). next for dichotomy means _{10 (N-1), ···} , supplied to the required means of secondary for dichotomy means 10 _2. For example, when the eigen equation is X ³ + BX ² + CX + D = 0, “3” becomes a coefficient by differentiating the third power term, so that this is detected and held, for example, and the secondary bisection means 10 ₂ To supply.

As shown in FIG. 2, the MAX value is the sum of the maximum values that can be taken by each of the elements a ₁₁ , a ₂₂ , a ₃₃ ,..., A _NN which are diagonal elements in an N-order square matrix. It is. The maximum value that each element can take is determined by the number of bits of each element. The maximum value is “8” if it is 3 bits without a sign, and the maximum value is “31” if it is 6 bits with a sign. It is. Since this sum is a MAX value, if it is 3 bits without a sign in a 3 × 3 matrix, “8 + 8 + 8 = 24”, and if it is 6 bits with a sign in a 3 × 3 matrix, “31 + 31 + 31 = 93”. "

N-order bisection means 10 _N , (N−1) -order bisection means 10 _(N−1) ,... Are respectively N, (N-1),. Means 12 are provided.

N-order bisection means 10 _N , (N−1) -order bisection means 10 _(N−1) ,... Are provided with the output from the preceding means, zero, and the MAX value as inputs. Then, N following a dichotomy means ₁₀ N, (N-1) following a dichotomy means _{10 (N-1), ···} , in the secondary for dichotomy means 10 _2, the each dichotomy calculating means 12 Two initial values selected from among the initial values are given, and the two initial values given to each of the dichotomy calculation means 12 are set in the corresponding dichotomy calculation means 12 so as to sandwich different solutions. Is done.

The dichotomy calculation means 12 is configured as shown in FIG. The bisection calculation unit 12 includes an intermediate value calculation unit 21, a first function value calculation unit 22, a second function value calculation unit 23, and a numerical value supply control unit 24. The intermediate value calculation means 21 obtains an intermediate value that is the value of the midpoint of two points corresponding to these values for the two input values. For example, with respect to the function F (X) shown in FIG. 4, the solution of the equation of F (X) = 0 is obtained by the bisection method as follows. Initially, when initial values X0 and X1 are given, (X0 + X1) / 2 is obtained as an intermediate value and set as output OUT. Next, the output OUT is set to X2, and since F (X2) and F (X0) have different signs, X0 is used to obtain (X0 + X2) / 2 and set as the output OUT. Although not the example of FIG. 4, when F (X2) and F (X1) have different signs, X1 is used to obtain (X1 + X2) / 2. In FIG. 4, (X0 + X2) / 2 obtained above is defined as an output OUT. Next, the output OUT is set to X3, and the signs of F (X3) and F (X2) are different, so X2 is used to obtain (X3 + X2) / 2 and set as the output OUT. In the same manner, such repeated calculation is performed. In this way, it approaches the solution.

  The first function value calculation means 22 obtains a function value using the intermediate value obtained by the intermediate value calculation means 21 as a variable in the function of the corresponding degree equation. The first function value calculation means 22 substitutes the output of the intermediate value calculation means 21 for the variable of the N-order function when the dichotomy calculation means 12 is used as the N-order bisection method means. Find the function value. Further, when the dichotomy calculation means 12 is used as an (N-1) degree bisection means, an intermediate value is added to the variable of the (N-1) degree function obtained by differentiating the N order function. A function value is obtained by substituting the output of the calculation means 21. Similarly, when the dichotomy calculation means 12 is used as a secondary dichotomy means, the intermediate value calculation means 21 is added to the variable of the quadratic function obtained by differentiating the N-order function several times. The function value is obtained by substituting the output of.

  The second function value calculating means 23 uses one of the two input values X0 and X1 (here, X0) or the previous intermediate value output from the intermediate value calculating means 21 as a variable in the function of the corresponding degree equation. Substituting for a function value. The second function value calculating means 23 substitutes one of the above values for the variable of the N-order function when the dichotomy computing means 12 is used as the N-order bisection means. Ask for. Further, when the dichotomy calculation means 12 is used as the (N-1) degree bisection means, any one of the variables of the (N-1) degree function obtained by differentiating the N order function is any of the above. A function value is obtained by substituting these values. Similarly, when the dichotomy calculation means 12 is used as a secondary dichotomy means, any one of the values described above is used as a variable of the quadratic function obtained by differentiating the N-order function several times. Substituting for the function value.

  The numerical value supply control unit 24 selects one of the values used in the previous intermediate value calculation based on the sign of the function value obtained by the first function value calculation unit 22 and the second function value calculation unit 23, The intermediate value calculated by the intermediate value calculating means 21 is supplied to the intermediate value calculating means 21 together with the intermediate value. The numerical value supply control means 24 confirms that the two inputs supplied to the intermediate value calculation means 21 are two values sandwiching the solution, that is, for example, the positional relationship between X1 and X2 shown in FIG. This is a circuit for securing.

  The number of repetitive calculations in the bisection calculation unit 12 is calculated by counting the number of calculations by the calculation number control unit 20 or referring to the output of the first function value calculation unit 22 or the second function value calculation unit 23. Control is performed by detecting that the difference between the output and zero is within a predetermined range.

The means according to the above configuration is realized when the computer executes a program for solving an eigen equation corresponding to the flowchart shown in FIG. The computer generates an eigen equation based on each element of the given Nth order square matrix (S11). Following this step S11, a solution is obtained when the function of the eigen equation generated above is differentiated into a linear function (S12).

The solution obtained in step S12, 0 (zero) and the above MAX value are given to the secondary bisection means to obtain the solution (S13), and whether the predetermined number of operations has been reached (or the first function value calculation means) 22 or the output of the second function value calculation means 23 is detected (whether the difference between the output and zero is within a predetermined range) (S14).

  In step S13 described above, processing corresponding to the flowchart shown in FIG. That is, the intermediate value is obtained using the given two input values (S21), and the first function value is obtained by substituting the intermediate value into the function variable of the order (here, 2) as already described. (S22). Further, the second function value is obtained by substituting one value of the two input values or the previous intermediate value for the variable of the function of the order (here 2) as already described (S23).

  Subsequent to step S23, based on the sign of the first function value and the sign of the second function value, one of the two values used in the previous intermediate value calculation is selected, and the intermediate value is calculated together with the calculated intermediate value. (S24). In response to this, an intermediate value is obtained using the given two input values (S25), it is detected whether the predetermined number of calculations have been performed (S26), and if the predetermined number of calculations has not been performed, Returning to step S22, the process is continued, and the process is terminated when a predetermined number of calculations are performed.

When the process corresponding to the flowchart of FIG. 6 is completed, the process proceeds from step S14 to step S15 in FIG. 5, and the solution obtained in step S13, 0 (zero), and the MAX value are given to the third-order bisection method. A solution is obtained (S15), whether the predetermined number of calculations has been reached (or referring to the output of the first function value calculation means 22 or the second function value calculation means 23, and the difference between the output and zero is predetermined. (S16). Also in step S15, the processing described with reference to the flowchart of FIG. 6 is performed. When the predetermined number of calculations is reached, the process proceeds to the solution processing by the quaternary bisection method that is the next order, and so on. Processing is performed using the solution obtained by increasing the order and the previous processing, 0 (zero), and the MAX value as input values.

Then, the process finally proceeds to the solution processing by the N-order bisection method, and the solution obtained in the previous step (solution of the (N−1) -order equation), 0 (zero), and the MAX value are divided into the N-order bisection. And the solution is obtained (S17), whether the predetermined number of calculations has been reached (or referring to the output of the first function value calculating means 22 or the second function value calculating means 23, Whether the difference from zero is within a predetermined range) is detected (S18). In step S17 as well, the process described with reference to the flowchart of FIG. 6 is performed, and when the predetermined number of calculations has been reached, the solution of the eigen equation has been obtained, and the solution process ends.

Next, a description will be given of an embodiment of an eigen equation solving apparatus configured by hardware. Figure 7 is a block diagram according to an embodiment of the solving device characteristic equations corresponding to square matrix of three rows and three columns are shown. This eigen equation solving apparatus includes an equation generating means 41, an initial value generating circuit 42 as an initial value giving means, a first group block 43 as a secondary bisection means, and a second group as a tertiary bisection means. The block 44 and the control circuit 49 are configured as main components.

The equation generation means 41 receives a numerical value of a 3 × 3 square matrix and generates a corresponding eigen equation . In practice, the equation generation means 41 obtains a coefficient of the cubic equation by matrix calculation. In the Nth-order eigen equation , the coefficient relating to the Nth-order term is 1, and here, the coefficient in the third-order term of the cubic equation is 1. Further, assuming that the coefficient in the second-order term is B, the coefficient in the first-order term is C, and the value of the constant term is D, the equation generating means 41 obtains B, C, and D, and these are obtained as an initial value generation circuit. 42.

The initial value generation circuit 42 includes a divider 45 that performs division so that 3 is a denominator, and a register 47 that outputs shifters 46 and 3 that perform a left shift of 1 bit. The initial value generating circuit 42 creates a solution of a linear equation obtained by differentiating the cubic equation twice. The coefficient B in the quadratic term output from the equation generating means 41 is “3” by the divider 45. Divide by. The solution (B / −3) of the linear equation (6X + 2B = 0) obtained by differentiating the cubic equation (X ³ + BX ² + CX + D = 0) twice by the divider 45 is obtained and input to the first group block 43. In the above, the divider 45 is a number obtained by subtracting the solution of the linear equation obtained by differentiating the eigen equation of the N-order square matrix (N−1) times from the number of constant terms of the linear equation. Is the numerator, the coefficient of the first-order term of the first-order equation is the denominator, and is expressed in the form of an irreducible fraction , the (N-1) th-order term of the N-order equation is expressed by the number constituting the denominator of the solution. A division means for dividing the coefficient is constructed. Here, the number constituting the denominator can be exemplified by a prime number obtained by factoring the above denominator, and includes a multiplication value of these prime numbers.

On the other hand, the shifter 46 shifts B to the left by 1 bit. A 1-bit left shift by the shifter 46 means multiplying by 2 and 2B is obtained. Also, 3 is output by the register 47. The first group block 43 and the second group block 44 are provided with bisection circuits 50 ₁ to 50 ₅ that constitute a bisection calculation means having the same configuration.

The bisection circuits 50 ₁ to 50 ₅ are configured as shown in FIG. The bisection circuits 50 ₁ to 50 ₅ include an adder 51 and a shifter 52 that performs 1-bit right shift, and the adder 51 and the shifter 52 constitute intermediate value calculation means for obtaining an intermediate value for two input values.

The bisection circuits 50 ₁ to 50 ₅ include function value calculation circuits 53 and 54. The function value calculation circuits 53 and 54 are configured as shown in FIG. The function value calculation circuits 53 and 54 include multipliers 61 to 64, an adder 65, and a selector 66. The multiplier 61 takes the input value X as two inputs and outputs X ² . The multiplier 62 receives the input value X and the output X ² of the multiplier 61 as inputs, and outputs X ³ . The multiplier 63 receives the input value X and B sent from the initial value generation circuit 42 or 3 which is the output of the register 47, and outputs BX ² or 3X ² . The multiplier 64 receives the input value X and C or 2B sent from the initial value generation circuit 42, and outputs CX or 2BX.

The selector 66 selectively outputs “0” input from one side or X ³ output from the multiplier 62 in accordance with the enable signal EN output from the control circuit 49. The output of the selector 66, the outputs of the multipliers 63 and 64, and C or D are input to the adder 65, and the added value is output from the adder 65.

Registers 47 to 3 are input to the multiplier 63 of the bisection circuits 50 ₁ and 50 ₂ , and B is input to the multiplier 63 of the bisection circuits 50 ₃ , 50 ₄ , and 50 ₅ . 2B is input to the multiplier 64 of the bisection circuits 50 ₁ , 50 ₂ , and C is input to the multiplier 64 of the bisection circuits 50 ₃ , 50 ₄ , 50 ₅ . C is input to the adder 65 of the bisection circuit 50 ₁ , 50 ₂ , and D is input to the adder 65 of the bisection circuit 50 ₃ , 50 ₄ , 50 ₅ .

  The output of the function value calculation circuit 53 is given to the control terminal of the selector 55, and the output of the function value calculation circuit 54 is given to the control terminal of the selector 56. The selector 55 outputs “1” if the control terminal signal S 2 is greater than 0, and outputs “0” if the control terminal signal S 2 is less than 0. The selector 56 outputs “1” if the control terminal signal S 1 is greater than 0, and outputs “0” if the control terminal signal S 1 is less than 0.

The outputs of the selectors 55 and 56 are given to the negative exclusive OR circuit 57, and the output of the negative exclusive OR circuit 57 is given to the control terminals of the selectors 58 and 59. The selector 58 selects and outputs the intermediate value that is the output of the shifter 52 if the signal S3 at the control terminal is 1, and selects and outputs the input value X0 if the signal S3 at the control terminal is 0. If the signal S3 at the control terminal is 0, the selector 59 selects and outputs the intermediate value that is the output of the shifter 52. If the signal S3 at the control terminal is 1, the selector 59 selectively outputs the input value X1. In this manner, the selectors 55 and 56, the negative exclusive OR circuit (EX-NOR) 57, and the selectors 58 and 59 are based on the sign of the function value obtained by the function value calculation circuits 53 and 54, and the previous intermediate value. One of the values used for the calculation is selected, and the numerical value supply control means for supplying to the adder 51 constituting the intermediate value calculation means together with the intermediate value calculated by the intermediate value calculation means is constituted.

As shown in FIG. 7, “0” is given as the input value X0 of the bisection circuits 50 ₁ and 50 ₃ via the signal line 48A, and the MAX value described above via the signal line 48 becomes the bisection circuit. It is given as an input value X1 of 50 ₂ and 50 ₅ . When the input values X0 and X1 of the bisection circuits 50 ₁ to 50 ₅ are put together, as shown in the following Table 1, each outputs the output of the previous group block.

For example, the control circuit 49 monitors whether or not the difference between the sum of the eigenvalue outputs of the bisection circuits 50 ₁ to 50 ₅ and the sum of the matrix diagonal elements is close to zero, and detects whether the predetermined number of computations has been reached. Alternatively, the output of the function value calculation circuits 53 and 54 is referred to detect whether the difference from zero is within a predetermined range, and the number of repeated calculations is controlled. Alternatively, a counter that counts the number of shift operations is mounted in the bisection circuit 50 ₁ to 50 ₅ , and when this counter reaches the specified number of calculations (fixed internally or variable by external input), the result of the shift operation is displayed. An output configuration can also be adopted.

Next, an embodiment of an eigen equation solving apparatus corresponding to a 4 × 4 square matrix was configured by hardware. As shown in FIG. 10, this apparatus comprises an equation generating means 71, an initial value generating circuit 72 as an initial value giving means, a first group block 73 as a secondary bisection means, and a tertiary bisection means. A certain second group block 74, a third group block 75 which is a quadratic bisection means, and a control circuit 79 are configured as main components.

The equation generating means 71 receives a numerical value of a 4 × 4 square matrix and generates a corresponding eigen equation . In practice, the equation generating means 71 obtains a coefficient of a quartic equation by matrix calculation. In the Nth-order eigen equation , the coefficient relating to the Nth-order term is 1, and here, the coefficient in the fourth-order term of the quartic equation is 1. Also, assuming that the coefficient in the third-order term is B, the coefficient in the third-order term is C, the coefficient in the second-order term is D, and the value of the constant term is E, the equation generating means 71 is B, C, D, E is obtained, and these are sent to the initial value generating circuit 72 which is an initial value giving means.

In the initial value generation circuit 72, the solution of the linear equation obtained by differentiating the Nth order equation (N-1) times, the number obtained by adding a minus to the number of constant terms of the first order equation as a numerator, The exponent for 2 obtained when the coefficient of the first-order term of the linear equation is expressed in the form of an irreducible fraction, and the denominator of the solution is primed and expressed in the form using an exponent. The shifter 76 that performs 2-bit right shift, which is a shift means that shifts the coefficient of the (N−1) -th order term of the Nth-order equation to the right, a multiplier 77 that multiplies by 3, and a 1-bit left shift A shifter 46 is provided, and a register 47 for outputting 3 and a register 78 for outputting 2 are provided. The initial value generation circuit 72 creates a solution of a linear equation obtained by differentiating the quaternary equation three times. The coefficient B in the third-order term output from the equation generation means 71 is shifted by 2 bits to the right by the shifter 76. Divide by “4”. The solution (B / −4) of the linear equation (24X + 6B = 0) obtained by differentiating the quartic equation (X ⁴ + BX ³ + CX ² + DX + E = 0) three times by the shifter 76 is obtained and input to the first group block 73.

A multiplier 77 for multiplying 3 multiplies B by 3 to obtain 3B. By applying the above 3B and C to the shifter 46 that performs the left shift for 1 bit, 6B and 2C are obtained by the left shift. The output 3 of the register 47 that outputs 3 is passed through the shifter 46 twice to obtain 12. The output 2 of the register 78 that outputs 2 is passed through the shifter 46 to obtain 4. These are used as coefficients of an equation when the quartic equation (X ⁴ + BX ³ + CX ² + DX + E = 0) is differentiated 1 to 3 times.

The first group block 73, the second group block 74, and the third group block 75 are provided with the bisection circuits 80 ₁ to 80 ₉ shown in FIG. Although the bisection circuits 80 ₁ to 80 ₉ have the block configuration shown in FIG. 8, the configuration of the function value calculation circuits 53 and 54 is different.

The function value calculation circuits 53 and 54 are configured as shown in FIG. The function value calculation circuits 53 and 54 include multipliers 91 to 96, an adder 99 and selectors 97 and 98. The multiplier 91 takes the input value X as two inputs and outputs X ² . The multiplier 92 receives the input value X and the output X ² of the multiplier 91 as inputs, and outputs X ³ . The multiplier 93 receives the input value X and the output X ³ of the multiplier 92 as inputs, and outputs X ⁴ . The multiplier 94 receives X ³ which is the output of the multiplier 92 and B or 4 sent from the initial value generation circuit 72 as inputs, and outputs BX ³ or 4X ³ . The multiplier 95 inputs X ² which is the output of the multiplier 91 and C, 3B or 12 sent from the initial value generation circuit 42 and outputs CX ² , 3BX ² or 12X ² . The multiplier 96 receives the input value X and D, 2C, or 6B sent from the initial value generation circuit 72, and outputs DX, 2CX, or 6BX.

The selector 97 selectively outputs “0” input from one side or X ⁴ output from the multiplier 93 in accordance with the enable signal EN 1 output from the control circuit 49. The selector 98 selectively outputs “0” input from one side or BX ³ (or 4X ³ ) which is the output of the multiplier 94 in accordance with the enable signal EN2 output from the control circuit 49. The output of the selectors 97 and 98, the output of the multipliers 95 and 96, and any of E, D, and 2C are input to the adder 99, and the added value is output from the adder 99.

4 is input to the multipliers 94 of the bisection circuits 80 ₃ , 80 ₄ , and 80 ₅ , and B is input to the multipliers 94 of the bisection circuits 80 ₆ to 80 ₉ . 12 is input to the multiplier 95 of the bisection circuits 80 ₁ and 80 ₂ , and 3B is input to the multiplier 95 of the bisection circuits 80 ₃ , 80 ₄ , and 80 ₅ , and the bisection circuits 80 ₆ to 80 ₉ C is input to the multiplier 95. 6B is input to the multiplier 96 of the bisection circuits 80 ₁ and 80 ₂ , and 2C is input to the multiplier 96 of the bisection circuits 80 ₃ , 80 ₄ , and 80 ₅ , and the bisection circuits 80 ₆ to 80 ₉ D is input to the multiplier 95. 2C is input to the adder 99 of the bisection circuits 80 ₁ , 80 ₂ , D is input to the adder 99 of the dichotomy circuits 80 ₃ , 80 ₄ , 80 ₅ , and the adder 99 of the bisection circuits 80 ₆ to 80 ₉ E is input to the adder 99.

As shown in FIG. 10, “0” is given as the input value X0 of the bisection circuits 80 ₁ , 80 ₃ , and 80 ₆ via the signal line 48 A, and the MAX value described above is obtained via the signal line 48. This is given as the input value X1 of the bisection circuit 80 ₂ , 80 ₅ , 80 ₉ . When the input values X0 and X1 of the bisection circuits 80 ₁ to 80 ₉ are put together, as shown in the following Table 2, each outputs the output of the previous group block.

The control circuit 79 monitors, for example, whether the difference between the sum of the eigenvalue outputs of the bisection circuits 80 ₁ to 80 ₉ and the sum of the diagonal elements of the matrix is close to zero, and detects whether the predetermined number of computations has been reached. Alternatively, with reference to the outputs of the function value calculation circuits 53 and 54, it is detected whether the difference between the output and zero is within a predetermined range, and the number of repeated calculations is controlled. Or to implement a counter that counts the shift operation execution count dichotomy circuit 80 ₁ to 80 _9, the result of the shift operation when this counter reaches a specified number of times of operations (variable by fixed or external input internally) An output configuration can also be adopted.

According to the hardware configuration apparatus described above, the initial value for the bisection method can be automatically calculated, the square root calculator can be eliminated, and the number of dividers can be reduced. Further, in the case of a matrix having a power-of-two size, it can be configured using a circuit using a right shift, and division is not necessary. Since it is possible to reuse the dichotomy circuit with the same configuration, the design period can be shortened , and the parallel arithmetic processing and the shared configuration of the arithmetic units are adopted, so the variation can be increased. It is rich in extensibility. In addition to easily adding the bisection calculation end condition according to the usage, the value output by the former bisection circuit is the initial value for the latter bisection circuit, and even if an error occurs, the bisection method is used. Since the convergence destination is the same, it has the effect of not being affected by the error of the previous stage calculation, and since the denominator of the divider is a fixed value, there is no need for countermeasures against divergence. In addition, since the bisection circuit is operated in parallel, an ultra-high speed output is possible, and there is an advantage that the gate scale can be reduced by sharing one dichotomy circuit.

The block diagram which shows the 1st Example of the solving apparatus of the eigen equation which concerns on this invention. The figure which shows the square matrix of N row N column used as the process target in the Example of the solving apparatus of the eigen equation which concerns on this invention. The block diagram which shows the principal part structure of the 1st Example of the solving apparatus of the eigen equation which concerns on this invention. The figure for demonstrating the procedure of the solution by a bisection method. The flowchart for demonstrating operation | movement of the 1st Example of the solving apparatus of the eigen equation which concerns on this invention. The flowchart for demonstrating operation | movement of the 1st Example of the solving apparatus of the eigen equation which concerns on this invention. The block diagram of the Example which comprised the solution apparatus of the cubic eigenequation which concerns on this invention with the hardware. The principal part block diagram of the Example which comprised the solution apparatus of the cubic eigenequation which concerns on this invention with the hardware. The block diagram which shows the principal part structure of the Example shown in FIG. The block diagram of the Example which comprised the solution apparatus of the 4th eigen equation which concerns on this invention with the hardware. The principal part block diagram of the Example which comprised the solution apparatus of the quartic eigen equation which concerns on this invention with the hardware.

10 _N , 10 _(N−1) ,... 10 _N N, (N−1) Secondary bisection method 11 Initial value assignment unit 12 Bisection method calculation unit 13 Equation generation unit 20 Calculation frequency control unit 21 Intermediate Value calculation means 22 First function value calculation means 23 Second function value calculation means 24 Numerical value supply control means 41 Equation generation means 42 Initial value generation circuit 43 First group block 44 Second group block 49 Control circuit 51 Adder 52 , 76 Shifter 53 Function value calculation circuit 54 Function value calculation circuit 55, 56, 58, 59, 66 Selector 57 Negative exclusive OR circuit 65, 99 Adder 71 Equation generation means 72 Initial value generation circuit 73 First group block 74 The second group blocks 75 third group block 79 the control circuit 97 and 98 the selector 80 ₁ -80 ₉ dichotomy circuit 50 ₁ -50 ₅ dichotomy circuit 61-64,77,91-96 multiplier 0 ₆ -80 ₉ dichotomy

Claims (8)

A solution of a linear equation obtained by differentiating an eigen equation of an N-order square matrix (N-1) times in which each order coefficient is an integer and each element is constituted by a number represented by a binary number , When the number of constant terms in the following equation is minus, the numerator is used, and the coefficient of the first order term of the linear equation is used as the denominator. When expressed in the form of an irreducible fraction, the denominator of the solution is constructed. Dividing means for dividing the coefficient of the (N-1) th order term of the Nth order equation by number and / or using an exponent by factoring the denominator of the solution of the first order equation when N is a multiple of 2 An initial value generating circuit having a shift means for shifting the coefficient to the right in correspondence with an index for 2 obtained when
Two dichotomy circuits for finding one solution based on two initial values using a bisection method, the maximum of each of the output of the initial value generation circuit, zero, and each of the diagonal elements in the N-order square matrix A first group block having a MAX value which is a sum of values as an input to the dichotomy circuit;
.., (N-1) blocks having the dichotomy circuit up to the (N-1) th circuit, each of which receives the MAX value, zero and the output of the previous group block as inputs. An eigen equation solving apparatus, comprising: The bisection circuit is
For two input values, an intermediate value calculating means for obtaining an intermediate value that is a value of a midpoint between two points corresponding to these values;
A first function value calculating means for obtaining a function value as a variable in a function of the corresponding degree equation;
A second function value calculating means for obtaining a function value using one of the two input values or the previous intermediate value as a variable in the function of the corresponding degree equation;
Based on the sign of the function value obtained by the first and second function value calculating means, one of the values used for the previous intermediate value calculation is selected, together with the intermediate value calculated by the intermediate value calculating means. The eigen-equation solving apparatus according to claim 1, further comprising: a numerical value supply control unit that supplies the intermediate value calculation unit. An N-order bisection method for obtaining N solutions of an eigen equation of an N-order square matrix by using a bisection method, and a minimum value and a maximum value of a function F (X) in the N-order equation F (X) = 0. The (N-1) degree bisection method obtained by the (N-1) degree equation which is a derivative of the N degree equation, the function F '(X) in the (N-1) degree equation F' (X) = 0. (N-2) a bisection method for the order (N-2) which is a derivative of the (N-1) degree equation, (N-2) a quadratic equation f (X) ) = 0 , a quadratic bisection means for obtaining a minimum value and a maximum value of the function f (X) by a quadratic equation that is a derivative of the cubic equation;
A solution of a linear equation that is a derivative of the quadratic equation is created, and a MAX value that is the sum of the zero value and the maximum value that each of the diagonal elements in the N-order square matrix can take is calculated. An initial value giving means for giving to the legal means,
Solving an eigen equation characterized in that the N-th order dichotomy means, (N-1) second-order dichotomy means,... Execute processing with the output from the preceding means, zero, and the MAX value as inputs. apparatus. N-th order bisection means, (N-1) second-order dichotomy means, respectively, comprise N, (N-1), ... bisection calculation means,
4. The eigenequation solving apparatus according to claim 3, wherein each of the bisection calculation means obtains one solution by using a bisection method based on two initial values. The bisection method is
For two input values, an intermediate value calculating means for obtaining an intermediate value that is a value of a midpoint between two points corresponding to these values;
A first function value calculating means for obtaining a function value as a variable in a function of the corresponding degree equation;
A second function value calculating means for obtaining a function value using one of the two input values or the previous intermediate value as a variable in the function of the corresponding degree equation;
Based on the sign of the function value obtained by the first and second function value calculating means, one of the values used for the previous intermediate value calculation is selected, together with the intermediate value calculated by the intermediate value calculating means. The eigen equation solving apparatus according to claim 4, further comprising: a numerical value supply control unit that supplies the intermediate value calculation unit. Computer
An N-order bisection method for obtaining N solutions of an eigen equation of an N-order square matrix by using a bisection method, and a minimum value and a maximum value of a function F (X) in the N-order equation F (X) = 0. The (N-1) degree bisection method obtained by the (N-1) degree equation which is a derivative of the N degree equation, the function F '(X) in the (N-1) degree equation F' (X) = 0. (N-2) a bisection method for the order (N-2) which is a derivative of the (N-1) degree equation, (N-2) a quadratic equation f (X) ) = 0 , a quadratic bisection means for obtaining a minimum value and a maximum value of the function f (X) by a quadratic equation that is a derivative of the cubic equation;
A solution of a linear equation that is a derivative of the quadratic equation is created, and a MAX value that is the sum of the zero value and the maximum value that each of the diagonal elements in the N-order square matrix can take is calculated. Means for giving initial values to legal means;
Function as
The N-th order bisection means, (N-1) second-order dichotomy means,... Are controlled so as to execute processing with the output from the preceding means, zero, and the MAX value as inputs. Eigen equation solving program. N-th order bisection means, (N-1) second-order dichotomy means, respectively, comprise N, (N-1), ... bisection calculation means,
7. The program for solving an eigen equation according to claim 6, wherein each of the bisection computing means obtains one solution by using a bisection method based on two initial values. The bisection method is
For two input values, an intermediate value calculating means for obtaining an intermediate value that is a value of a midpoint between two points corresponding to these values;
A first function value calculating means for obtaining a function value as a variable in a function of the corresponding degree equation;
A second function value calculating means for obtaining a function value using one of the two input values or the previous intermediate value as a variable in the function of the corresponding degree equation;
Based on the sign of the function value obtained by the first and second function value calculating means, one of the values used for the previous intermediate value calculation is selected, together with the intermediate value calculated by the intermediate value calculating means. A numerical value supply control means for supplying to the intermediate value calculation means, The eigen equation solving program according to claim 7.

Images