Square Jacobi SVD HDL Optimized

Fixed-point singular value decomposition

Since R2023a

• 

×

Libraries:
Fixed-Point Designer HDL Support / Matrices and Linear Algebra / Matrix Factorizations

Description

Use the Square Jacobi SVD HDL Optimized block to perform singular value decomposition (SVD) on square matrices using the two-sided Jacobi algorithm. Given a square matrix A, the Square Jacobi SVD HDL Optimized block uses the two-sided Jacobi method to produce a vector s of nonnegative elements and unitary matrices U and V such that A = U*diag(s)*V'.

Examples

How to Use Square Jacobi SVD HDL Optimized Block

Use the Square Jacobi SVD HDL Optimized block to compute the singular value decomposition (SVD) of square matrices.

Open Script

Implement HDL Optimized SVD in Feedforward Fashion Without Backpressure

Implement a hardware-efficient singular value decomposition (SVD) using the Square Jacobi SVD HDL Optimized block in a feedforward fashion without backpressure.

Open Script

Implement HDL Optimized SVD with Backpressure Signal and HDL FIFO Block

Implement hardware-efficient singular value decomposition (SVD) using the Square Jacobi SVD HDL Optimized block with backpressure control and an HDL FIFO block.

Open Model

Ports

Input

A — Square matrix A

real or complex square matrix

Square n-by-n matrix A, specified as a real or complex square matrix.

If the matrix A has a fixed-point data type, the matrix must use signed binary-point scaling. Slope and bias scaling and unsigned fixed-point types are not supported.

Data Types: single | double | fixed point

validIn — Whether input is valid

Boolean scalar

Whether input is valid, specified as a Boolean scalar. This control signal indicates when the data from the A input port is valid. When this value is 1 (true) and the value at ready is 1 (true), the block captures the values at the A input port. When this value is 0 (false), the block ignores the input samples.

After sending a true validIn signal, a delay may occur before the ready signal is false. To ensure all data is processed, you must wait until the ready signal is false before sending another true validIn signal.

Data Types: Boolean

readyIn — Whether downstream block is ready

Boolean scalar

Whether downstream block is ready, specified as a Boolean scalar. This control signal monitors the ready port of the downstream block. When the readyIn value is 1 (true), and the value at validOut is 1 (true), the block outputs data to the downstream block. When the readyIn value is 0 (false), the downstream block is not ready to accept data. The Square Jacobi SVD HDL Optimized block pauses on the output stage and the ready signal remains 0 (false) until the readyIn signal is high.

Data Types: Boolean

restart — Whether to clear internal states

Boolean scalar

Whether to clear internal states, specified as a Boolean scalar. When this value is 1 (true), the block stops the current calculation and clears all internal states. When this value is 0 (false) and the validIn value is 1 (true), the block begins a new subframe.

Data Types: Boolean

Output

s — Singular values

column vector

Singular values, returned as a column vector of length n. The Singular Values are nonnegative and returned in descending order such that s(1) >= s(2) >= ... >= s(n). Singular values are returned with the same data type as the input matrix A.

Data Types: single | double | fixed point

U — Left singular vectors

unitary n-by-n matrix

Left singular vectors, returned as a unitary n-by-n matrix.

For fixed-point and scaled-double inputs, U is returned as a signed fixed-point or scaled-double fi with the same word length as A and fraction length equal to two less than the word length. One of these integer bits is used for the sign. The other integer bit allows +1 to be represented exactly.

For floating-point input, U has the same data type as A.

Data Types: single | double | fixed point

V — Right singular vectors

unitary n-by-n matrix

Right singular vectors, returned as a unitary n-by-n matrix.

For fixed-point and scaled-double inputs, V is returned as a signed fixed-point or scaled-double fi with the same word length as A and fraction length equal to two less than the word length. One of these integer bits is used for the sign. The other integer bit allows +1 to be represented exactly.

For floating-point input, V has the same data type as A.

Data Types: single | double | fixed point

validOut — Whether output data is valid

Boolean scalar

Whether the output data is valid, returned as a Boolean scalar. This control signal indicates when the data at the output ports U, S, and V are valid. When this value is 1 (true), the output data is valid. When this value is 0 (false), the output data is not valid. Transfer of data to the downstream block occurs only when both the validOut and readyIn signals are high.

Data Types: Boolean

ready — Whether block is ready

Boolean scalar

Whether the block is ready, returned as a Boolean scalar. This control signal indicates when the block is ready for new input data. When this value is 1 (true) and the validIn value is 1 (true), the block accepts input data in the next time step. When this value is 0 (false), the block ignores input data in the next time step.

After sending a true validIn signal, there may be some delay before the ready signal is false. To ensure all data is processed, you must wait until the ready signal is false before sending another true validIn signal.

Data Types: Boolean

Parameters

Dimension of matrix A — Dimension of square matrix A

n (default) | positive integer-valued scalar

Dimension of square matrix A, specified as a positive integer-valued scalar.

Programmatic Use

Block Parameter: n

Type: string

Values: positive integer-valued scalar

Default: n

Number of Jacobi iterations — Number of iterations of Jacobi algorithm

10 (default) | positive integer

Number of iterations of the Jacobi algorithm, specified as a positive integer. Most sources indicate that 10 iterations is sufficient for the Jacobi algorithm to converge [7][8][9][10].

Programmatic Use

Block Parameter: nIterations

Type: string

Values: positive integer-valued scalar

Default: 10

Select outputs — Block outputs

UsV (default) | Us | sV | s

Block outputs, specified as UsV, Us, sV, or s.

Programmatic Use

Block Parameter: outputOption

Type: string

Values: UsV | Us | sV | s

Default: UsV

Signal type — Complexity of input matrix A

real (default) | complex

Complexity of the input matrix A, specified as real, or complex.

Programmatic Use

Block Parameter: complexity

Type: string

Values: real | complex

Default: real

Tips

• The Square Jacobi SVD HDL Optimized block computes the singular value decomposition in place. Set the fixed-point data type of the input n-by-n matrix A with enough precision and enough headroom to avoid overflow.

  First, use the fixed.singularValueUpperBound function to determine the upper bound on the singular values. Then define the integer length based on the value of the upper bound, with one additional bit for the sign, another additional bit for intermediate CORDIC growth, and one more bit for intermediate growth to compute the Jacobi rotations. Compute the fraction length based on the integer length and the desired word length.

  svdUpperBound = fixed.singularValueUpperBound(n,n,max(abs(A(:))))
  additionalBitGrowth = 3;
  integerLength = ceil(log2(svdUpperBound)) + additionalBitGrowth
  wordLength = 16
  fractionLength = wordLength - integerLength

• The behavior of the Square Jacobi SVD HDL Optimized block is equivalent to [U,s,V] = fixed.jacobiSVD(A). The fixed.JacobiSVD function uses the same algorithm as the Square Jacobi SVD HDL Optimized, with the same output data types. However, there may be small numerical differences in the least-significant bit between the function and the block.

• The behavior of the Square Jacobi SVD HDL Optimized block is equivalent to [U,s,V] = fixed.svd(A,'econ','vector') when A is a square matrix.

Algorithms

Jacobi Singular Value Decomposition

The Square Jacobi SVD HDL Optimized block uses a two-sided Jacobi algorithm for singular value decomposition (SVD) [2][3][4]. Compared to the sequential Golub-Kahan-Reinsch algorithm for SVD [5], the Jacobi algorithm has inherent parallelism and performs better for FPGA and ASIC applications [6]. The Jacobi method is an iterative algorithm. Use the Number of Jacobi iterations parameter to set the number of iterations necessary for convergence. Most sources indicate that 10 iterations is sufficient for the Jacobi algorithm to converge [7][8][9][10].

AMBA AXI Handshake Process

This block uses the AMBA AXI handshake protocol on both the input and the output side [1]. The valid/ready handshake process is used to transfer data and control information. This two-way control mechanism allows both the manager and subordinate to control the rate at which information moves between manager and subordinate.

On the input side, the validIn signal indicates when the upstream data is available. The ready signal indicates that the block can accept the data. Transfer of data from the upstream block occurs only when both the validIn and ready signals are high.

On the output side, the validOut signal indicates the solution data is available. The readyIn signal indicates when the downstream block can accept data. Transfer of data to the downstream block occurs only when both the validOut and readyIn signals are high.

When the readyIn signal is low, the block pauses on the output stage and the ready signal remains low. This configuration allows a stall from the downstream block to back-propagate to the upstream block.

To use the Square Jacobi SVD HDL Optimized block in feed-forward fashion without back pressure from the downstream block, feed a constant Boolean 'true' to the readyIn port.

Block Timing

The latency of the Square Jacobi SVD HDL Optimized block depends on the size (n), complexity, and word length (wl) of the input matrix A, and the number of iterations (nIterations) of the two-sided Jacobi algorithm, as summarized in the table.

• If the data type of A is fixed point, then wl is the word length.

• If the data type of A is double precision, then wl is 53.

• If the data type of A is single precision, then wl is 24.

Signal Complexity	validIn to validOut
Real	(wl*2+31)*(n-1+rem(n,2))*nIterations+2+nextpow2(n)*(nextpow2(n)+1)/2+3
Complex	(wl*6+48)*(n-1+rem(n,2))*nIterations+2+nextpow2(n)*(nextpow2(n)+1)/2+3

For example, assume that validIn asserts before ready, meaning that the upstream data source is faster than the Square Jacobi SVD HDL Optimized block. Additionally, assume that readyIn is always asserted, meaning that the downstream consumer of the data is faster than the Square Jacobi SVD HDL Optimized.

In the figure:

• A1 is the first A matrix, U1 is the first U matrix, s1 is the first s vector, V1 is the first V matrix, and so on.

• validIn to validOut — Goes from a successful matrix input to the block starting to output the solution.

• After a successful solution output, the block is ready again at the next clock cycle.

Hardware Resource Utilization

This block supports HDL code generation using the Simulink^® HDL Workflow Advisor. For an example, see HDL Code Generation and FPGA Synthesis from Simulink Model (HDL Coder) and Implement Digital Downconverter for FPGA (DSP HDL Toolbox).

This example data was generated by synthesizing the block on a Xilinx^® Zynq^®-7000 xc7z100 SoC. The synthesis tool was Vivado^® v2022.1 (win64).

Signal Type: Real

The following parameters were used for synthesis.

• Block parameters:

  • n = 8

  • nIterations = 10

• Input data type: sfix32_En25

• Target frequency: 90 MHz

These tables show the post place-and-route resource utilization results and timing summary, respectively.

Resource	Usage	Available	Utilization
Slice LUTs	71541	277400	25.79%
Slice Registers	35781	554800	6.45%
DSPs	256	2020	12.67%
Block RAM Tile	0	755	0%

	Value
Requirement	11.111 ns (90 MHz)
Data Path Delay	11.007 ns
Slack	0.085 ns
Clock Frequency	90.69 MHz

Signal Type: Complex

The following parameters were used for synthesis.

• Block parameters:

  • n = 8

  • nIterations = 10

• Input data type: sfix32_En25

• Target frequency: 60 MHz

The following tables show the post place-and-route resource utilization results and timing summary, respectively.

Resource	Usage	Available	Utilization
Slice LUTs	196506	277400	70.84%
Slice Registers	85150	554800	15.35%
DSPs	1344	2020	66.53%
Block RAM Tile	0	755	0%

	Value
Requirement	16.667 ns (60 MHz)
Data Path Delay	16.572 ns
Slack	0.076 ns
Clock Frequency	60.27 MHz

References

[1] Arm Developer. "AMBA AXI and ACE Protocol Specification Version E." https://developer.arm.com/documentation/ihi0022/e/AMBA-AXI3-and-AXI4-Protocol-Specification/Single-Interface-Requirements/Basic-read-and-write-transactions/Handshake-process.

[2] Jacobi, Carl G. J., "Über ein leichtes Verfahren die in der Theorie der Säcularstörungen vorkommenden Gleichungen numerisch aufzulösen." Journal fur die reine und angewandte Mathematik 30 (1846): 51–94.

[3] Forsythe, George E. and Peter Henrici. "The Cyclic Jacobi Method for Computing the Principal Values of a Complex Matrix." Transactions of the American Mathematical Society 94, no. 1 (January 1960): 1-23.

[4] Shiri, Aidin and Ghader Khosroshahi. "An FPGA Implementation of Singular Value Decomposition", ICEE 2019: 27th Iranian Conference on Electrical Engineering, Yazd, Iran, April 30–May 2, 2019, 416-22, IEEE.

[5] Golub, Gene H. and Charles F. Van Loan. Matrix Computations, 4th ed. Baltimore, MD: Johns Hopkins University Press, 2013.

[6] Athi, Mrudula V., Seyed R. Zekavat, and Alan A. Struthers. "Real-Time Signal Processing of Massive Sensor Arrays via a Parallel Fast Converging SVD Algorithm: Latency, Throughput, and Resource Analysis." IEEE Sensors Journal 16, no. 18 (January 2016): 2519-26. https://doi.org/10.1109/JSEN.2016.2517040.

[7] Brent, Richard P., Franklin T. Luk, and Charles Van Loan. "Computation of the Singular Value Decomposition Using Mesh-Connected Processors." Journal of VLSI and Computer Systems 1, 3 (1985): 242–70.

[8] Hemkumar, Nariankadu D. A Systolic VLSI Architecture for Complex SVD. Master’s thesis, Rice University, 1991.

[9] Duryea, R. A. Finite Precision Arithmetic in Singular Value Decomposition Architectures. Ph.D. thesis, Cornell University, 1987.

[10] Cavallaro, Joseph R. and Franklin T. Luk. 1987. "CORDIC Arithmetic for an SVD Processor." 1987 IEEE 8th Symposium on Computer Arithmetic (ARITH), Como, Italy, May 18-21, 1987, 113-20. IEEE. https://doi.org/10.1109/ARITH.1987.6158686.

Extended Capabilities

HDL Code Generation

Generate Verilog and VHDL code for FPGA and ASIC designs using HDL Coder™.

Note

When generating code for large matrices set the configuration parameter HDL Code Generation > Global Settings > Ports tab Check for DUT pin count exceeding I/O Threshold to Warning or None. To learn more about this setting, see DUT Port Configuration Parameters (HDL Coder).

HDL Coder™ provides additional configuration options that affect HDL implementation and synthesized logic.

HDL Architecture

This block has one default HDL architecture.

HDL Block Properties

General
ConstrainedOutputPipeline	Number of registers to place at the outputs by moving existing delays within your design. Distributed pipelining does not redistribute these registers. The default is 0. For more details, see ConstrainedOutputPipeline (HDL Coder).
InputPipeline	Number of input pipeline stages to insert in the generated code. Distributed pipelining and constrained output pipelining can move these registers. The default is 0. For more details, see InputPipeline (HDL Coder).
OutputPipeline	Number of output pipeline stages to insert in the generated code. Distributed pipelining and constrained output pipelining can move these registers. The default is 0. For more details, see OutputPipeline (HDL Coder).

Restrictions

Supports fixed-point data types only. Fixed-point data types must use signed binary-point scaling. Slope and bias scaling and unsigned fixed-point types are not supported.

Version History

Introduced in R2023a