JP7560765B2 - Calculation method, calculation device and program - Google Patents

Description

The present invention relates to a calculation method, a calculation device and a program technology.

A data structure called an embedded graph exists in various fields such as networks, geographic information science, and image engineering. An embedded graph is defined by combining a graph, which is a set of multiple vertices and the edges connecting those vertices, with the positions of those vertices. For example, in a network, a graph can be constructed by corresponding network nodes to vertices and network links to edges. In this case, an embedded graph can be found by matching the physical positions of the network nodes or the node coordinates when visualizing the network to the vertex positions.

In geographic information science, boundary data such as national and prefectural borders, coastlines, and lake shorelines are generally stored as embedded graphs. Boundaries are represented by densely plotting vertices on the boundaries and connecting the edges. In the field of image engineering, embedded graphs are used to store data related to shapes and areas. For example, data such as object shapes in vector images, depth boundaries in depth maps, subject shapes and texture area shapes in natural images are represented as embedded graphs. Boundaries are represented by edges by plotting vertices on the boundaries of shapes and areas.

In the embedded graphs shown above, there is a great advantage to simplifying the embedded graph by reducing the number of vertices and edges as much as possible while preserving the shape of the embedded graph as much as possible (hereinafter referred to as simplifying the embedded graph, or simply simplification).

In a network, the more vertices and edges there are, the more detailed the data can be expressed, but it also becomes difficult to grasp the overall network configuration at a glance, and the data volume becomes huge, placing a heavy load on drawing. If the embedded graph for this network could be simplified, the network configuration could be presented in a visually easy-to-understand manner, and it would be possible to reduce the number of vertices and edges, compress the data, and reduce the load on drawing. In geographic information studies, boundaries can be accurately represented by densely plotting vertices on the boundaries, but this results in a huge amount of data.

By simplifying boundary data, it is possible to reduce the amount of data required for transmission and storage, and to generate geographic information with simplified boundaries that is visually easier to understand. In image engineering, the more vertices and edges there are, the more detailed shape and area data can be retained and more accurately represented, but the amount of data becomes enormous, and the amount of code required for transmission and storage increases.

If this shape and area can be simplified, the number of vertices and edges can be reduced, thereby reducing the amount of code, while maintaining the accuracy of the representation as much as possible.
As an invention for achieving the above simplification, an embedded graph simplification method has been proposed (see Patent Document 2). A high-speed processing method (two-dimensional version) (see Patent Document 3) and a high-speed processing method (multidimensional version) (see Patent Document 4) have also been proposed.

The above high-speed processing method employs Fast Multiple SVT (see Non-Patent Document 1), which performs high-speed calculations of multiple Singular Value Thresholding (SVT) (see Patent Document 4) in parallel. The algorithm is shown in FIG. 16. In the algorithm shown in FIG. 16A and FIG. 16B, the reciprocal square root and the difference between square roots are calculated in the third line g ^-1 and h ^-1 and the fourth line σ _2, respectively. This reciprocal square root is the bottleneck in the calculation speed of the algorithm shown in FIG. 16A and FIG. 16B.

In addition, the calculation of the difference between square roots is prone to cancellation of digits, which can easily lead to errors. Furthermore, in the algorithms shown in Figures 16A and 16B, only the square root calculation is required in the square root difference calculation on line 4, and only the reciprocal square root is used in other places.

Now, the reciprocal square root a = 1/√A of a positive real number A is calculated repeatedly and extensively in the form of normal calculations in reflected light and scattered light simulations in the field of computer graphics (CG).

To reduce the amount of calculation, the Fast Inverse Square Root (FastInvSqrt) method was invented, which speeds up the calculation of the reciprocal square root by several times by avoiding the calculation of the square root. This technology is implemented in game software that uses CG (see Non-Patent Document 2). In addition, a modified FastInvSqrt method has been invented as a high-precision version of the FastInvSqrt method (see Non-Patent Document 3).

By adopting this FastInvSqrt method or the modified FastInvSqrt method to calculate the reciprocal square root in the Fast Multiple SVT described above, it is expected that the calculation speed will be improved.

JP 2016-221829 A JP 2017-211706 A JP 2018-082249 A JP 2019-046196 A

Takamoto Sasaki, Masaki Kitahara, Jun Shimizu, "Fast Singular Value Thresholding for Low-Rank Optimization," 16th Forum on Information Science and Technology, 2017 M. Robertson, “A Brief History of InvSqrt,” Bachelor Thesis, University of New Brunswick, 2012. C. J. Walczyk, ``A Modification of the Fast Inverse Square,'' MDPI Computation, vol. 7, no. 3, 2019

However, Fast Multiple SVT requires square root difference calculations, so ultimately the square root is required, and then a reciprocal calculation is required. As a result, the speedup mentioned above is not achieved.

As such, a graph simplification device using Fast Multiple SVT cannot process quickly, and cannot perform graph drawing or graph processing quickly.

In view of the above circumstances, the present invention aims to provide a technology for performing calculations including square roots more quickly.

One aspect of the present invention is a calculation method including a first reciprocal square root step in which the computer calculates the reciprocal square root of a positive real number A using the fast reciprocal square root method, a second reciprocal square root step in which the computer calculates the reciprocal square root of a positive real number B using the fast reciprocal square root method, a subtraction step in which the computer subtracts B from A, a first multiplication step in which the computer multiplies the calculation result of the first reciprocal square root step by the calculation result of the second reciprocal square root step, a second multiplication step in which the computer multiplies the calculation result of the first multiplication step by the calculation result of the subtraction step, an addition step in which the computer adds the calculation result of the first reciprocal square root step by the calculation result of the second reciprocal square root step, and a division step in which the computer divides the calculation result of the second multiplication step by the calculation result of the addition step.

One aspect of the present invention is a program for causing a computer to execute the above calculation method.

One aspect of the present invention is a calculation device including a first reciprocal square root unit that calculates the reciprocal square root of a positive real number A using the fast reciprocal square root method, a second reciprocal square root unit that calculates the reciprocal square root of a positive real number B using the fast reciprocal square root method, a subtraction unit that subtracts B from A, a first multiplication unit that multiplies the calculation result of the first reciprocal square root unit by the calculation result of the second reciprocal square root unit, a second multiplication unit that multiplies the calculation result of the first multiplication unit by the calculation result of the subtraction unit, an addition unit that adds the calculation result of the first reciprocal square root unit to the calculation result of the second reciprocal square root unit, and a division unit that divides the calculation result of the second multiplication unit by the calculation result of the addition unit.

The present invention makes it possible to perform calculations involving square roots faster.

FIG. 1 is a diagram illustrating a configuration of an information processing device including a computing device. FIG. 2 is a block diagram showing a configuration of a computing device 10A. FIG. 2 is a block diagram showing a computing device 20. FIG. FIG. 2 is a block diagram showing a configuration of a computing device 10B. FIG. 4 is a block diagram showing a computing device 40. FIG. 2 is a block diagram showing a configuration of a computing device 10C. FIG. 2 is a block diagram showing a configuration of a computing device 10D. FIG. 2 is a block diagram showing a configuration of a computing device 10E. FIG. 2 is a block diagram showing a configuration of a computing device 10F. FIG. 13 is a diagram illustrating an outline of a graph simplification process. FIG. 1 illustrates an example of the configuration of a graph simplifying device. FIG. 13 is a diagram illustrating an example of the configuration of a local linear alignment unit. FIG. 13 is a diagram for explaining an operation of arranging vectors of adjacent sides. FIG. 1 shows an algorithm illustrating the solution to the local linear alignment problem. FIG. 1 shows an algorithm illustrating the solution to the local linear alignment problem. FIG. 1 illustrates an algorithm for singular value threshold processing. FIG. 1 illustrates an algorithm for singular value threshold processing.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described in detail with reference to the drawings.
1 is a diagram showing the configuration of an information processing device 1 including a calculation device 10 in an embodiment. The information processing device 1 includes an input device 3, a calculation device 10, and an output device 5. The input device 3 inputs input data such as numerical values to the calculation device 10. The calculation device 10 performs calculations using the input data and outputs the calculation results to the output device 5.

The computing device 10 includes a CPU (Central Processing Unit), memory, auxiliary storage device, etc., which are connected by a bus, and performs computational processing by executing a computation program. All or part of the functions of the computing device 10 may be realized using hardware such as an ASIC (Application Specific Integrated Circuit), a PLD (Programmable Logic Device), or an FPGA (Field Programmable Gate Array). The computation program may be recorded on a computer-readable recording medium. Examples of computer-readable recording media include portable media such as flexible disks, optical magnetic disks, ROMs, CD-ROMs, and semiconductor storage devices (e.g., SSDs: Solid State Drives), and storage devices such as hard disks built into computer systems. The computation program may be transmitted via a telecommunications line.

Below, the first to sixth embodiments of the calculation device 10 will be described. After that, a graph simplification process will be described as an application example of the calculation device 10. Note that the "fast reciprocal square root calculation unit" in each embodiment calculates the reciprocal square root using the fast reciprocal square root method.

[First embodiment]
Hereinafter, a calculation device 10A, which is the calculation device 10 in the first embodiment, will be described. Fig. 2 is a block diagram showing the configuration of the calculation device 10A that calculates the reciprocal square root and the square root difference in the embodiment. The calculation device 10A is a calculation device that receives positive real numbers A and B from the input device 3 and outputs a = 1/√A, b = 1/√B, and c = √A - √B to the output device 5. The calculation device 10A includes high-speed reciprocal square root calculation units 11 and 21, a subtraction unit 12, multiplication units 17 and 117, an addition unit 13, and a division unit 14.

When a positive real number A is input to calculation device 10A, A is input to fast reciprocal square root calculation unit 11 and subtraction unit 12. When a positive real number B is input, B is input to fast reciprocal square root calculation unit 21 and subtraction unit 12. Fast reciprocal square root calculation unit 11 outputs a = 1/√A to subtraction unit 12, addition unit 13, and output device 5. Fast reciprocal square root calculation unit 21 outputs b = 1/√B to subtraction unit 12, addition unit 13, and output device 5. Subtraction unit 12 outputs A - B to multiplication unit 117.

The multiplication unit 17 outputs ab to the multiplication unit 117. The multiplication unit 117 outputs (A-B)ab to the division unit 14. The addition unit 13 outputs a+b to the division unit 14. The division unit 14 outputs (A-B)ab/(a+b) as c to the output device 5.

Here, (A-B)ab/(a+b)=√A-√B as follows.
√A-√B=(√A-√B)(√A+√B)/(√A+√B)
=(A-B)/(√A+√B)
Where:
√A+√B=(1/√A+1/√B)(√A√B)=(a+b)/(ab)
Therefore, (A-B)/(√A+√B)=(A-B)ab/(a+b).

From the above, calculation device 10A outputs a = 1/√A, b = 1/√B, and c = √A - √B to output device 5. Calculation device 10A calculates the reciprocal square root, but does not calculate √A or √B. Therefore, it outputs c without calculating √A or √B. Furthermore, by rationalizing the numerator, it is possible to prevent loss of digits in √A - √B compared to when calculating √A and √B.

Figure 3 is a block diagram showing a calculation device 20 that calculates √A and √B and outputs a, b, and c as in the conventional case. The calculation device 20 includes square root calculation units 15 and 25, a subtraction unit 22, and division units 24 and 34.

In the calculation device 20, when a positive real number A is input, the square root calculation unit 15 outputs √A to the subtraction unit 22 and the division unit 24. When a positive real number B is input, the square root calculation unit 25 outputs √B to the subtraction unit 22 and the division unit 34.

The division unit 24 outputs a = 1/√A. The division unit 34 outputs b = 1/√B. The subtraction unit 22 outputs c = √A - √B.

In order to compare the amount of calculations, the amount of calculations for each calculation will be explained using Figure 4. Figure 4 shows the time required to perform each calculation 1,000,000 times in C++, with addition being 1 flop. In Figure 4, sqrt(x) indicates the amount of calculation required to calculate the square root and 1/sqrt(x) indicates the amount of calculation required to calculate the reciprocal square root using standard library functions in C++. Also, fastInvSqrt(x) indicates the amount of calculation required by the Fast Inverse Square Root method using Newton's method once. fastInvSqrt2(x) indicates the amount of calculation required by the Fast Inverse Square Root method using Newton's method twice. fastInvSqrt3(x) indicates the amount of calculation required by the Fast Inverse Square Root method using Newton's method three times. mFastInvSqrt(x) indicates the amount of calculation required by the modified Fast Inverse Square Root method.

According to H.A. Thant, et. al., “Mobile Agents Based Load Balancing Method for Parallel Applications,” 6th Asia-Pacific Symposium on Information and Telecommunication Technologies, Yangon, 2005, if the computational effort of one floating-point addition is also 1 flop, then subtraction and multiplication require 1 flop, while division and square root calculations require 4 flops. Furthermore, the reciprocal square root calculation using the FastInvSqrt method can be estimated to be 1 flop, as shown in Figure 4.

When a, b, and c are calculated using a conventional calculation device 20, the total amount of calculation is 17 flops. On the other hand, when calculated using the calculation device 10A according to this embodiment, the total amount of calculation is 10 flops. Therefore, compared to the conventional calculation device 20, it can be estimated that the calculation device 10A according to this embodiment reduces floating-point operations by 7 flops, or approximately 41.2%.

[Second embodiment]
Hereinafter, a calculation device 10B, which is the calculation device 10 in the second embodiment, will be described. Fig. 5 is a block diagram showing the configuration of the calculation device 10B that calculates the reciprocal square root of the sum and the difference, and the square root difference of the sum and the difference, in the embodiment. The calculation device 10B is a calculation device that receives positive real numbers X and e (X>e>0) from the input device 3 and outputs a = 1/√(X+e), b = 1/√(X-e), and c = √(X+e)-√(X-e) to the output device 5. The calculation device 10B includes high-speed reciprocal square root calculation units 31 and 41, a subtraction unit 32, multiplication units 27, 37, and 47, addition units 23 and 33, and a division unit 44.

When a positive real number X is input to calculation device 10B, X is input to addition unit 23 and subtraction unit 32. When a positive real number e is input, e is input to addition unit 23, subtraction unit 32, and multiplication unit 27. Addition unit 23 outputs X+e to fast reciprocal square root calculation unit 31. Subtraction unit 32 outputs X-e to fast reciprocal square root calculation unit 41. Multiplication unit 27 outputs 2e to multiplication unit 47.

The fast reciprocal square root calculation unit 31 outputs a = 1/√(X+e) to the multiplication unit 37, the addition unit 33, and the output device 5. The fast reciprocal square root calculation unit 41 outputs b = 1/√(X-e) to the multiplication unit 37, the addition unit 33, and the output device 5. The multiplication unit 37 outputs ab = (1/√(X+e)) (1/√(X-e)) to the multiplication unit 47. The multiplication unit 47 outputs 2eab to the division unit 44. The addition unit 33 outputs a + b = 1/√(X+e) + 1/√(X-e) to the division unit 44. The division unit 44 outputs 2eab/(a + b) as c to the output device 5. The fact that 2eab/(a+b)=√(X+e)-√(X-e) can be shown by setting A in the first embodiment to X+e and B to X-e.

From the above, calculation device 10B outputs a = 1/√(X+e), b = 1/√(X-e), and c = √(X+e) - √(X-e) to output device 5. Calculation device 10B calculates the reciprocal square root, but does not calculate √(X+e) or √(X-e). Therefore, it outputs c without calculating √(X+e) or √(X-e).

Figure 6 is a block diagram showing, as a reference example, a calculation device 40 that calculates √(X+e) and √(X-e) and outputs a, b, and c as in the conventional manner. The calculation device 40 includes square root calculation units 35 and 45, subtraction units 42 and 52, an addition unit 43, and division units 54 and 64.

When positive real numbers X and e are input to calculation device 40, addition unit 43 outputs X+e to square root calculation unit 35. Subtraction unit 42 outputs X-e to square root calculation unit 45. Square root calculation unit 35 outputs √(X+e) to division unit 54 and subtraction unit 52. Square root calculation unit 45 outputs √(X-e) to division unit 64 and subtraction unit 52.

The division unit 54 outputs a = 1/√(X+e). The division unit 64 outputs b = 1/√(X-e). The subtraction unit 52 outputs c = √(X+e) - √(X-e).

When a, b, and c are calculated using a conventional calculation device 40, the total amount of calculation is 19 flops. On the other hand, when calculated using the calculation device 10B according to this embodiment, the total amount of calculation is 12 flops. Therefore, compared to the conventional calculation device 40, the calculation device 10B according to this embodiment can be estimated to reduce floating-point operations by 7 flops, or approximately 36.8%.

[Third embodiment]
Hereinafter, a calculation device 10C, which is the calculation device 10 in the third embodiment, will be described. Fig. 7 is a block diagram showing the configuration of the calculation device 10C in the embodiment, which calculates the second singular value of an M x 2 matrix, the inverse of the sum of the singular values, and the inverse of the difference of the singular values. In this embodiment, M ≥ 3, and M = 2 will be described in the fourth embodiment. The calculation device 10C is a calculation device that receives an M x 2 matrix Y = [y ₁ , y ₂ ] from the input device 3, and outputs the second singular value σ ₂ , the inverse of the sum of the singular values 1/(σ ₁ + σ ₂ ), and the inverse of the difference of the singular values 1/(σ ₁ - _{σ 2} ) to the output device 5.

The calculation device 10C includes the calculation device 10B described in the second embodiment. The calculation device 10C also includes a decomposition unit 110, inner product units 16, 26, and 36, a subtraction unit 62, multiplication units 57, 67, 77, and 87, an addition unit 53, and a square root calculation unit 55.

In the calculation device 10C, when an M×2 matrix Y=[ _y1 , _y2 ] is input, Y is input to the decomposition unit 110. The decomposition unit 110 decomposes the M×2 matrix Y into column vectors _y1 and _y2 . The decomposition unit 110 outputs _y1 to the inner product units 16 and 36. The decomposition unit 110 outputs _y2 to the inner product units 26 and 36.

The dot product unit 16 calculates the dot product a between _y1 and _y1 , and outputs a to the adder unit 53, the multiplier unit 67, and the output device 5. The dot product unit 26 calculates the dot product c between _y2 and _y2 , and outputs c to the adder unit 53, the multiplier unit 67, and the output device 5. The dot product unit 36 calculates the dot product b between _y1 and _y2 , and outputs b to the multiplier unit 77 and the output device 5.

Addition unit 53 outputs f=a+c to calculation device 10B and output device 5. Multiplication unit 67 outputs ac to subtraction unit 62. Multiplication unit 77 outputs b ² to subtraction unit 62. Subtraction unit 62 outputs d=ac-b ² to square root calculation unit 55 and output device 5. Square root calculation unit 55 outputs e=√d to multiplication unit 57 and output device 5. Multiplication unit 57 outputs 2e to calculation device 10B.

Calculation device 10B outputs 1/√(f+2e) as 1/(σ ₁ +σ ₂ ) to output device 5. Calculation device 10B outputs 1/√(f-2e) as 1/(σ ₁ -σ ₂ ) to output device 5. Calculation device 10B outputs √(f+2e)-√(f-2e) as 2σ ₂ to multiplication unit 87. Multiplication unit 87 outputs σ ₂ to output device 5.

Here, 1/√(f±2e) is 1/(σ ₁ ±σ ₂ ) as follows: According to Non-Patent Document 1, the sum and difference of the singular values σ ₁ and σ ₂ of an M×2 matrix are σ ₁ ±σ ₂ =√(tr(Y ^T Y)±2√(det(Y ^T Y))).

tr( ^YTY ) = a (= the dot product of _y1 and _y1 ) + c (= the dot product of _y2 and _y2 ) = f. det( ^YTY ) = a (= the dot product of _y1 and _y1 ) × c (= the dot product of _y2 and _y2 ) - ^b2 (= (the dot product b of _y1 and _y2 ) ² ) = ac - ^b2 = d. Therefore, √(det( ^YTY )) = √d = e.

Therefore, (tr( ^YTY )±2(det( ^YTY )))=(f±2e). Therefore, 1/(f±2e)=1/( _σ1 ± _σ2 ).

As shown in FIG. 7, the calculation device 10C outputs not only the second singular value σ ₂ , the reciprocal of the sum of the singular values 1/(σ ₁ +σ ₂ ), and the reciprocal of the difference of the singular values 1/(σ ₁ -σ ₂ ), but also a, b, c, d, e, and f to the output device 5.

The computational complexity of the computing device 10C will be described. The processing of the decomposition unit 110 simply decomposes a matrix into column vectors, so no floating-point calculations are performed (0 flops). The computational complexity of the inner product units 16, 26, and 36 is 2M-1 flops for an input of an M-th order column vector. As described above, the square root calculation by sqrt is 4 flops. Therefore, the total computational complexity of the computing device 10C is 6M+19 flops. As described above, the computing device 10B has a reduction effect of 7 flops, so the computing device 10C also has a reduction effect of 7 flops due to the computing device 10B.
[Fourth embodiment]
Hereinafter, a calculation device 10D, which is the calculation device 10 in the fourth embodiment, will be described. Fig. 8 is a block diagram showing the configuration of the calculation device 10D in the embodiment, which calculates the second singular value of a 2x2 matrix, the inverse of the sum of the singular values, and the inverse of the difference of the singular values. The calculation device 10D is a calculation device that receives a 2x2 matrix Y = [ _y1 , _y2 ] from the input device 3, and outputs the second singular value _σ2 , the inverse of the sum of the singular values 1/( _σ1 + _σ2 ), and the inverse of the difference of the singular values 1/( _σ1 - _σ2 ) to the output device 5.

The calculation device 10D includes the calculation device 10B described in the second embodiment. The calculation device 10D also includes a decomposition unit 120, inner product units 46 and 56, a determinant calculation unit 19, an absolute value calculation unit 18, multiplication units 97 and 107, and an addition unit 63.

In the calculation device 10D, when a 2×2 matrix Y=[y ₁ , y ₂ ] is input, Y is input to the decomposition unit 120. The decomposition unit 120 decomposes the 2×2 matrix Y into column vectors y ₁ and y _2. The decomposition unit 120 outputs y ₁ to the inner product unit 46. The decomposition unit 120 outputs y ₂ to the inner product unit 56.

The inner product unit 46 calculates the inner product a of _y1 and _y1 , and outputs a to the addition unit 63. The inner product unit 56 calculates the inner product c of _y2 and _y2 , and outputs c to the addition unit 63. The determinant calculation unit 19 calculates the determinant d of Y, and outputs d to the absolute value calculation unit 18 and the output device 5.

The addition unit 63 outputs f = a + c to the calculation device 10B and the output device 5. The absolute value calculation unit 18 outputs the absolute value e of d to the multiplication unit 97. The multiplication unit 97 outputs 2e to the calculation device 10B.

Calculation device 10B outputs 1/√(f+2e) as 1/(σ ₁ +σ ₂ ) to output device 5. Calculation device 10B outputs 1/√(f-2e) as 1/(σ ₁ -σ ₂ ) to output device 5. Calculation device 10B outputs √(f+2e)-√(f-2e) as 2σ ₂ to multiplication unit 107. Multiplication unit 107 outputs σ ₂ to output device 5.

Here, 1/√(f±2e) is 1/(σ ₁ ±σ ₂ ) as shown in the third embodiment. As shown in Fig. 8, the calculation device 10D outputs not only the second singular value σ ₂ , the reciprocal of the sum of the singular values 1/(σ ₁ +σ ₂ ), and the reciprocal of the difference of the singular values 1/(σ ₁ -σ ₂ ), but also d and f to the output device 5.

The calculation amount of the calculation device 10D will be described. The calculation amount of the determinant calculation unit 19 is 3 flops. The absolute value calculation unit 18 only evaluates the sign and inverts it if it is negative, so no floating point calculation is performed (0 flops). The total calculation amount by the calculation device 10D is 24 flops. As described above, the calculation device 10B has a reduction effect of 7 flops, so the calculation device 10D also has a reduction effect of 7 flops due to the calculation device 10B.
[Fifth embodiment]
Hereinafter, a calculation device 10E, which is the calculation device 10 in the fifth embodiment, will be described. Fig. 9 is a block diagram showing the configuration of the calculation device 10E in the embodiment, which calculates the SVT of an M x 2 matrix. In this embodiment, M ≥ 3, and M = 2 will be described in the sixth embodiment. The calculation device 10E receives an M x 2 matrix Y = [ _y1 , _y2 ] and a positive real number μ from the input device 3, performs singular value thresholding (SVT), and calculates a matrix Z shown in the following (1) as a result of the singular value thresholding.

In (1), _I2 is a 2 × 2 unit matrix. γ, δ, e, a, b, c, and d will be described later.

The calculation device 10E includes the calculation device 10C described in the third embodiment, a coefficient calculation device 200, and an M×2 matrix transformation device 300.

When an M×2 matrix Y=[y ₁ , y ₂ ] is input to the calculation device 10E, Y is input to the calculation device 10C, the coefficient calculation device 200, and the M×2 matrix transformation device 300. When a real number μ is input to the calculation device 10E, μ is input to the coefficient calculation device 200. As described in the third embodiment, the calculation device 10C outputs the second singular value σ ₂ , the reciprocal of the sum of the singular values 1/(σ ₁ +σ ₂ ), the reciprocal of the difference of the singular values 1/(σ ₁ -σ ₂ ), a, b, c, d, e, and f. Here, as shown in FIG. 9, g=1/(σ ₁ +σ ₂ ), h=1/(σ ₁ -σ ₂ ).

Of the outputs of the calculation device 10C, d, f, σ ₂ , g, and h are output to the coefficient calculation device 200. A, B, C, and E are output to the M×2 matrix transformation device 300.

The coefficient calculation device 200 receives d, f, σ ₂ , g, h, and μ as input. The coefficient calculation device 200 outputs γ and δ. The calculation method of γ and δ will be described. First, a sufficiently large real number is set as R. Specifically, the size of R can be about one tenth the maximum number of a single-precision floating-point number. Then, the coefficient calculation device 200 calculates γ and δ by dividing the case into the following four cases (a) to (d), and outputs them.

(a) When Y is a zero matrix. (b) When (a) does not apply and d = 0. (c) When (b) does not apply and h > R. (d) When (c) does not apply.

The following shows γ and δ output for each case. The reciprocal square root using the fast reciprocal square root method may be expressed as isqrt(·). For example, the reciprocal square root of a positive real number A calculated using the fast reciprocal square root method may be expressed as isqrt(A). The subscript + on the lower right of (·) ₊ indicates a ramp function. The ramp function outputs 0 if the input is a negative real number, and outputs the input real number as is if the input is a non-negative real number. The function min outputs the smallest value among the input numerical values.

(a): γ=0, δ=0
(b): γ=(1-μ×isqrt(f)) ₊ , δ=0
(c): γ=(1-(√2)×μ×isqrt(f)) ₊ , δ=0
(d): γ=(1-(μ-σ ₂ ) ₊ ×h) ₊ , δ=min(μ, σ ₂ )×g

The coefficient calculation device 200 outputs γ and δ to the M×2 matrix transformation device 300 according to the above case distinction. As a result, the M×2 matrix transformation device 300 has all the parameters included in (1) above, and uses them to output (1) to the output device 5. Note that when e=0, γδ/e in (1) is set to 0.

The calculation amount of the calculation device 10E will be described. The ramp function and the function min are mainly calculated by comparing real values, and no floating point calculation is performed (0 flop). When calculating according to the algorithm shown in FIG. 16B, the calculation amount is 12M+38 flops. On the other hand, the total calculation amount by the calculation device 10E is 12M+29 flops. From the above, it can be estimated that 9 flops of floating point calculations will be reduced.
Sixth Embodiment
Hereinafter, a calculation device 10F, which is the calculation device 10 in the sixth embodiment, will be described. Fig. 10 is a block diagram showing the configuration of the calculation device 10F that calculates the SVT of a 2x2 matrix in the embodiment. The calculation device 10F receives the 2x2 matrix Y = [ _y1 , _y2 ] and a positive real number μ from the input device 3, performs the above-mentioned SVT, and calculates the matrix Z shown in the following (1) as the result of the singular value threshold processing. Note that _yij is the i-th row, j-th column component of Y.

The function sign(.) in (2) is a sign function that outputs -1 when the input is negative, 0 when the input is 0, and +1 when the input is positive. γ, δ, and d will be explained later.

The calculation device 10F includes the calculation device 10D described in the fourth embodiment, a coefficient calculation device 201, and a 2x2 matrix transformation device 301.

When a 2×2 matrix Y=[y ₁ , y ₂ ] is input to the calculation device 10F, Y is input to the calculation device 10D, the coefficient calculation device 201, and the M×2 matrix transformation device 301. When a real number μ is input to the calculation device 10F, μ is input to the coefficient calculation device 201. As described in the third embodiment, the calculation device 10D outputs the second singular value σ ₂ , the reciprocal of the sum of the singular values 1/(σ ₁ +σ ₂ ), the reciprocal of the difference of the singular values 1/(σ ₁ -σ ₂ ), d, and f. Here, as shown in FIG. 10, g=1/(σ ₁ +σ ₂ ), and h=1/(σ ₁ -σ ₂ ).

Of the outputs of the calculation device 10D, d, f, σ ₂ , g, and h are output to the coefficient calculation device 201. d is output to the 2×2 matrix transformation device 300.

The coefficient calculation device 201 receives d, f, σ ₂ , g, h, and μ as input. The coefficient calculation device 201 outputs γ and δ. The calculation method of γ and δ will be described. First, a sufficiently large real number is set as R. Specifically, the size of R can be about one tenth the maximum number of a single-precision floating-point number. Then, the coefficient calculation device 200 calculates γ and δ by dividing the case into the following four cases (a) to (d), and outputs them.

(a) When Y is a zero matrix. (b) When (a) does not apply and d = 0. (c) When (b) does not apply and h > R. (d) When (c) does not apply.

The following shows γ and δ that are output for each case.
(a): γ=0, δ=0
(b): γ=(1-μ×isqrt(f)) ₊ , δ=0
(c): γ=(1-(√2)×μ×isqrt(f)) ₊ , δ=0
(d): γ=(1-(μ-σ ₂ ) ₊ ×h) ₊ , δ=min(μ, σ ₂ )×g

The coefficient calculation device 200 outputs γ and δ to the 2×2 matrix transformation device 301 based on the above case distinction. As a result, the 2×2 matrix transformation device 301 has all the parameters included in (2) above, and uses these to output (2) to the output device 5.

The calculation amount of the calculation device 10F will be described. When calculating according to the algorithm shown in FIG. 16B, the calculation amount is 41 flops. On the other hand, the total calculation amount by the calculation device 10F is 32 flops. From the above, it can be estimated that 9 flops of floating-point operations will be reduced.

Next, the graph simplification process will be described. Fig. 11 is a diagram showing an overview of the graph simplification process. In Fig. 11, G = (V, E, P) indicates a graph embedded in an M-dimensional space. Here, V and E are a set of vertices and edges, respectively, and P ∈ R ^{|V| × M} is the vertex coordinates (here, R is the set of all real numbers). Each row vector (p ₁ ) ^T , (p ₂ ) ^T , ..., (p _|v| ) ^T of P represents the coordinates of each vertex of the graph. In addition, the set of vertices with degree 2 is denoted as V~ = {v ∈ V | degv = 2}.

In the graph simplification process, as shown in Figure 11, an embedded graph with a distorted shape and many vertices is input, and an embedded graph that is locally linearly aligned is intermediately generated (S101), and finally unnecessary points are removed (S102) to obtain the desired graph with a simplified shape.

Figure 12 is a diagram showing an example configuration of a graph simplification device 500. The graph simplification device 500 receives a threshold λ and a graph G as input, and outputs a simplified graph G". The graph simplification device 500 includes a local linear alignment unit 510 and an unnecessary vertex removal unit 520. The local linear alignment unit 510 outputs G', which is obtained by locally linearly aligning the graph G using the threshold λ, to the unnecessary vertex removal unit 520. The unnecessary vertex removal unit 520 outputs G" in which unnecessary vertices have been removed from the vertices of the input graph G'.

Fig. 13 is a diagram showing an example of the configuration of the local linear alignment unit 510 in Fig. 12. As described above, the local linear alignment unit 510 outputs G', which is obtained by locally linearly aligning the graph G using the threshold value λ, to the unnecessary vertex removal unit 520. The local linear alignment unit 510 includes a convex optimization problem formulation unit 511, a convex optimization problem solution unit 512, and a coordinate information replacement unit 513.

First, the convex optimization problem formulation unit 511 will be described. FIG. 14 is a diagram for explaining the operation of arranging vectors of adjacent sides. The matrix L _V shown in FIG. 14 is a matrix for arranging vectors from v to adjacent vertices. In the elements of the matrix L _V shown in FIG. 14, all the places marked with "..." are 0. Also, when the coordinate of v is the kth row of P, "-1" in L _V shown in FIG. 14 is the kth column. By L _V P, a vector with v as the starting point and the coordinate of the k-1th row as the end point, and a vector with v as the starting point and the coordinate of the k+1th row as the end point are obtained. The operation of applying this L _V is a linear mapping.

If the number of turns is small while faithfully reproducing the shape of the original input graph, it can be said that local linear alignment of the graph has been successful. Here, the measure of faithful reproduction is the L1 norm, and the regularization of the number of turns of an edge is the kernel norm function, and the convex optimization problem formulation unit 511 formulates the optimization problem as shown in (3) below. Here, the kernel norm function is a function that calculates the sum of the singular values of the input matrix.

In order to solve the optimization problem of (3) above, Primal-Dual Splitting (see L. Condat, "A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms," Journal of Optimization Theory and Applications, 2013.) is used. FIG. 15 shows a specific procedure executed by the convex optimization problem solving unit 512. FIG. 15 is a diagram showing an algorithm showing a method for solving the local linear alignment problem. Note that f in prox _τf on the fourth line of FIG. 15 is the following (4).

In the algorithm shown in Figure 15, in the r loops from n = 1 to r from lines 3 to 11, it is shown that the loops from lines 6 to 10 are performed for all elements belonging to V~ mentioned above.

Therefore, lines 6 to 10 are executed r × (total number of elements belonging to V~) times. The following (5), calculated in line 8 of lines 6 to 10, is the proximity map of the kernel type norm.

The above (5) is an SVT using the threshold value λ of the matrix of the following (6).

The processing on line 8 takes up approximately 53.8% of the calculation time of the algorithm shown in Figure 15. Therefore, by calculating the SVT using the above-mentioned calculation devices 10E and 10F, the graph simplification process can be executed faster than in the past.

The coordinate information replacement unit 513 replaces the coordinate information with the vertex coordinates locally linearly aligned by the convex optimization problem solving unit 512, and outputs the locally linearly aligned G'.

This embodiment is applicable not only to graph simplification but also to all processes that perform SVT. For example, image false color removal, like graph simplification, is classified as a problem of regularizing a large number of small matrices.

As described above, according to this embodiment, the nucleus norm is expressed by a mixed norm without using singular values, thereby realizing SVT calculations that do not require SVD, thereby reducing the amount of calculations. Furthermore, the algorithm can be easily data-parallelized, allowing simultaneous processing of multiple matrices. If the algorithm can be data-parallelized, it can be speeded up by implementing it using a data-parallel architecture such as Single Instruction Multiple Data (SIMD), which is used in many CPUs installed in personal computers.

In the calculation devices 10A to 10F described above, the configurations that perform various calculations, such as the addition unit and the inner product unit, may be provided with a storage device such as a memory that temporarily stores the calculation results, and the calculation results may be temporarily stored in this storage device.

Although an embodiment of the present invention has been described in detail above with reference to the drawings, the specific configuration is not limited to this embodiment and also includes designs that do not deviate from the gist of the present invention.

The present invention is applicable to a computing device that performs square root calculations.

10, 10A, 10B, 10C, 10D, 10E, 10F, 20, 40... Calculation device, 11, 21, 31, 41... High speed reciprocal square root calculation section, 12, 22, 32, 42, 52... Subtraction section, 13, 23, 33, 43, 53, 63... Addition section, 14, 24, 34, 44, 54, 64... Division section, 15, 25, 35, 45, 55... Square root calculation section, 16, 26, 36, 46, 56... Inner product part, 17, 27 , 37, 47, 57, 67, 77, 87, 97, 107, 117 ... multiplication unit, 18 ... absolute value calculation unit, 19 ... determinant calculation unit, 110, 120 ... decomposition unit, 200, 201 ... coefficient calculation device , 300, 301 ... matrix conversion device, 500 ... graph simplification device, 510 ... local linear alignment unit, 511 ... convex optimization problem formulation unit, 512 ... convex optimization problem solving unit, 513 ... coordinate information replacement unit, 520 …Unnecessary vertex removal section

Claims (7)

a first reciprocal square root step in which the computer calculates the reciprocal square root of a positive real number A by a fast reciprocal square root method;
a second reciprocal square root step in which the computer calculates the reciprocal square root of the positive real number B using a fast reciprocal square root method;
A subtraction step in which the computer subtracts B from A;
a first multiplication step in which the computer multiplies a result of the first reciprocal square root step by a result of the second reciprocal square root step;
a second multiplication step in which the computer multiplies a result of the first multiplication step by a result of the subtraction step;
an addition step in which the computer adds a result of the calculation in the first reciprocal square root step and a result of the calculation in the second reciprocal square root step;
a division step in which the computer divides the result of the second multiplication step by the result of the addition step;
A calculation method that includes: a first addition step in which a computer adds a positive real number X and a positive real number e smaller than the real number X;
A subtraction step in which the computer subtracts e from X;
a first multiplication step in which the computer doubles e;
a first reciprocal square root step in which the computer calculates a reciprocal square root of the calculation result in the first addition step by using a fast reciprocal square root method;
a second reciprocal square root step in which the computer calculates a reciprocal square root of the calculation result in the subtraction step by a fast reciprocal square root method;
a second addition step in which the computer adds a result of the calculation in the first reciprocal square root step and a result of the calculation in the second reciprocal square root step;
a second multiplication step in which the computer multiplies a result of the first reciprocal square root step by a result of the second reciprocal square root step;
a third multiplication step in which the computer multiplies a result of the second multiplication step by a result of the subtraction step;
a division step in which the computer divides a result of the third multiplication step by a result of the second addition step;
A calculation method that includes: a first inner product step in which the computer calculates an inner product between first column vectors among first column vectors and second column vectors that configure an M×2 matrix;
a second dot product step in which the computer calculates a dot product between the second column vectors;
a third dot product step in which the computer calculates an dot product of the first column vector and the second column vector;
an addition step in which a computer adds a calculation result in the first dot product step and a calculation result in the second dot product step;
a first multiplication step in which the computer multiplies a result of the first inner product step by a result of the second inner product step;
a second multiplication step in which the computer multiplies the inner products calculated in the third inner product step;
a subtraction step in which the computer subtracts the calculation result in the second multiplication step from the calculation result in the first multiplication step;
a square root calculation step in which the computer calculates the square root of the calculation result in the subtraction step;
a third multiplication step in which the computer doubles the result of the square root calculation step;
Equipped with
A method for calculating the inverse of the sum of two singular values of an M×2 matrix, the inverse of the difference between two singular values, and one singular value by the method according to claim 2, where the calculation result in the addition step is X and the calculation result in the third multiplication step is e. A calculation method comprising the steps of executing each step of claim 3 , and further comprising a step of a computer calculating a singular value threshold process of an M×2 matrix using the inverse of the sum of two singular values and the inverse of the difference of the two singular values calculated by the calculation method of claim 3. An alignment step in which a computer locally linearly aligns vertices of a graph in an M-dimensional space;
a removing step in which the computer removes unnecessary edges and vertices from the vertices of the graph linearly arranged in the sorting step, based on angles between edges connecting the vertices;
Equipped with
The method according to claim 4, wherein in the alignment step, singular value threshold processing is performed using a kernicrotype norm function that calculates the sum of singular values. A program for causing a computer to execute the calculation method according to any one of claims 1 to 5. a first reciprocal square root unit that calculates a reciprocal square root of a positive real number A by a fast reciprocal square root method;
a second reciprocal square root unit that calculates the reciprocal square root of a positive real number B by a fast reciprocal square root method;
A subtraction unit that subtracts B from A;
a first multiplication unit that multiplies a calculation result in the first reciprocal square root unit by a calculation result in the second reciprocal square root unit;
a second multiplication unit that multiplies a result of the calculation in the first multiplication unit by a result of the calculation in the subtraction unit;
an adder that adds a calculation result of the first reciprocal square root unit and a calculation result of the second reciprocal square root unit;
a division unit that divides a calculation result in the second multiplication unit by a calculation result in the addition unit;
A computing device comprising:

Images