fixed.qrFixedpointTypes

Determine fixed-point types for transforming A and R and B to C=Q'B in-place, where QR=A is QR decomposition of A

Since R2021b

Syntax

``T = fixed.qrFixedpointTypes(m,max_abs_A,max_abs_B,precisionBits)``
``T = fixed.qrFixedpointTypes(m,max_abs_A,max_abs_B,precisionBits,regularizationParameter)``
``T = fixed.qrFixedpointTypes(___,maxWordLength)``

Description

example

````T = fixed.qrFixedpointTypes(m,max_abs_A,max_abs_B,precisionBits)` returns fixed-point types for A and B that guarantee no overflow will occur in the QR algorithm.The QR algorithm transforms A in-place into upper-triangular R and transforms B in-place into C=Q'B, where QR=A is the QR decomposition of A.```
````T = fixed.qrFixedpointTypes(m,max_abs_A,max_abs_B,precisionBits,regularizationParameter)` returns fixed-point types for transforming $\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]$ in-place to $R=Q\text{'}\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]$ and $\left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$ in-place to $C=Q\text{'}\left[\begin{array}{c}{0}_{n,p}\\ B\end{array}\right]$ where λ is the `regularizationParameter`, QR is the economy size QR decomposition of $\left[\begin{array}{c}\lambda {I}_{n}\\ A\end{array}\right]$, A is an m-by-n matrix, p is the number of columns in B, In = `eye(n)`, and 0n,p = `zeros(n,p)`. `regularizationParameter` is an optional parameter. If not supplied or empty, then the default value is used.```
````T = fixed.qrFixedpointTypes(___,maxWordLength)` specifies the maximum word length of the fixed-point types. `maxWordLength` is an optional parameter. If not supplied or empty, then the default value is used.```

Examples

collapse all

This example shows how to use `fixed.qrFixedpointTypes` to analytically determine fixed-point types for the computation of the QR decomposition.

Define Matrix Dimensions

Specify the number of rows in matrices $A$ and $B$, the number of columns in matrix $A$, and the number of columns in matrix $B$. This example sets $B$ to be the identity matrix the same size as the number of rows of $A$.

```m = 10; % Number of rows in matrices A and B n = 3; % Number of columns in matrix A```

Generate Matrices A and B

Use the helper function `realUniformRandomArray` to generate a random matrix $A$ such that the elements of $A$ are between $-1$ and $+1$. Matrix $B$ is the identity matrix.

```rng('default') A = fixed.example.realUniformRandomArray(-1,1,m,n); B = eye(m);```

Select Fixed-Point Types

Use `fixed.qrFixedpointTypes` to select fixed-point data types for matrices $A$ and $B$ that guarantee no overflow will occur in the transformation of $A$ in-place to $R={Q}^{\prime }A$ and $B$ in-place to $C={Q}^{\prime }B$.

```max_abs_A = 1; % Upper bound on max(abs(A(:)) max_abs_B = 1; % Upper bound on max(abs(B(:)) precisionBits = 24; % Number of bits of precision T = fixed.qrFixedpointTypes(m,max_abs_A,max_abs_B,precisionBits)```
```T = struct with fields: A: [0x0 embedded.fi] B: [0x0 embedded.fi] ```

`T.A` is the type computed for transforming $\mathit{A}$ to $\mathit{R}={\mathit{Q}}^{\prime }\mathit{A}$ in-place so that it does not overflow.

`T.A`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 29 FractionLength: 24 ```

`T.B` is the type computed for transforming $\mathit{B}$ to ${\mathit{C}=\mathit{Q}}^{\prime }\mathit{B}$ in-place so that it does not overflow.

`T.B`
```ans = [] DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 29 FractionLength: 24 ```

Use the Specified Types to Compute the QR Decomposition

Cast the inputs to the types determined by `fixed.qrFixedpointTypes``.`

```A = cast(A,'like',T.A); B = cast(B,'like',T.B);```

Accelerate `fixed.qrAB` by using `fiaccel` to generate a MATLAB executable (MEX) function.

`fiaccel fixed.qrAB -args {A,B} -o qrAB_mex`

Compute the QR decomposition.

`[C,R] = qrAB_mex(A,B);`

Extract the Economy-Size Q

The function `fixed.qrAB` transforms $\mathit{A}$ to $\mathit{R}={\mathit{Q}}^{\prime }\mathit{A}$ and $B$ to $C={Q}^{\prime }B$. In this example, $B$ is the identity matrix, so $Q={C}^{\prime }$ is the economy-size orthogonal factor of the QR decomposition.

`Q = C';`

Verify that Q is Orthogonal and R is Upper-Triangular

$Q$ is orthogonal, so ${Q}^{\prime }Q$ is the identity matrix within rounding error.

`I = Q'*Q`
```I = 1.0000 -0.0000 -0.0000 -0.0000 1.0000 -0.0000 -0.0000 -0.0000 1.0000 DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 62 FractionLength: 48 ```

$R$ is an upper-triangular matrix.

`R`
```R = 2.2180 0.8559 -0.5607 0 2.0578 -0.4017 0 0 1.7117 DataTypeMode: Fixed-point: binary point scaling Signedness: Signed WordLength: 29 FractionLength: 24 ```
`isequal(R,triu(R))`
```ans = logical 1 ```

Verify the Accuracy of the Output

To evaluate the accuracy of the `fixed.qrAB` function, compute the relative error.

`relative_error = norm(double(Q*R - A))/norm(double(A))`
```relative_error = 1.5208e-06 ```

Suppress `mlint` warnings.

`%#ok<*NOPTS>`

Input Arguments

collapse all

Number of rows in A, specified as a positive integer-valued scalar.

Data Types: `double`

Maximum of the absolute value of A, specified as a scalar.

Example: `max(abs(A(:)))`

Data Types: `double`

Maximum of the absolute value of B, specified as a scalar.

Example: `max(abs(B(:)))`

Data Types: `double`

Required number of bits of precision, specified as a positive integer-valued scalar.

Data Types: `double`

Regularization parameter, specified as a nonnegative scalar. Small, positive values of the regularization parameter can improve the conditioning of the problem and reduce the variance of the estimates. While biased, the reduced variance of the estimate often results in a smaller mean squared error when compared to least-squares estimates.

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `int64` | `uint8` | `uint16` | `uint32` | `uint64` | `fi`

Maximum word length of fixed-point types, specified as a positive integer.

If the word length of the fixed-point type exceeds the specified maximum word length, the default of `128` bits is used.

Data Types: `single` | `double` | `int8` | `int16` | `int32` | `int64` | `uint8` | `uint16` | `uint32` | `uint64` | `fi`

Output Arguments

collapse all

Fixed-point types for A and B, returned as a struct. The struct `T` has fields `T.A` and `T.B`. These fields contain `fi` objects that specify fixed-point types for A and B that guarantee no overflow will occur in the QR algorithm.

The QR algorithm transforms A in-place into upper-triangular R and transforms B in-place into C=Q'B where QR=A is the QR decomposition of A.

Tips

Use `fixed.qrFixedpointTypes` to compute fixed-point types for the inputs of these functions and blocks.

Algorithms

The number of integer bits required to prevent overflow is derived from the following bounds on the growth of R and C=Q'B [1]. The required number of integer bits is added to the number of bits of precision, `precisionBits`, of the input, plus one for the sign bit, plus one bit for intermediate CORDIC gain of approximately 1.6468 [2].

The elements of R are bounded in magnitude by

`$\mathrm{max}\left(|R\left(:\right)|\right)\le \sqrt{m}\mathrm{max}\left(|A\left(:\right)|\right).$`

The elements of C=Q'B are bounded in magnitude by

`$\mathrm{max}\left(|C\left(:\right)|\right)\le \sqrt{m}\mathrm{max}\left(|B\left(:\right)|\right).$`

References

[2] Voler, Jack E. "The CORDIC Trigonometric Computing Technique." IRE Transactions on Electronic Computers EC-8 (1959): 330-334.

Version History

Introduced in R2021b

expand all