Skip to content

gram_schmidt

qoptcraft.math.gram_schmidt

Stable Gram-Schmidt algorithm.

gram_schmidt(basis)

Gram-Schmidt algorithm to orthonormalize a basis.

Note

It turns out that the normal Gram-Schmidt algorithm suffers from numerical instability: Round-off errors can accumulate and destroy orthogonality of the resulting vectors. We introduce the modified Gram-Schmidt procedure to help remedy this issue.

Parameters:

Name Type Description Default
basis list[spmatrix]

basis to orthonormalize.

 required

Returns:

Type Description
list[spmatrix] | list[NDArray]

list[spmatrix]: orthonormalized basis.
References

Algorithm can be found in https://www.math.uci.edu/~ttrogdon/105A/html/Lecture23.html

Source code in qoptcraft/math/gram_schmidt.py 
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def gram_schmidt(basis: list[spmatrix] | list[NDArray]) -> list[spmatrix] | list[NDArray]:
    """Gram-Schmidt algorithm to orthonormalize a basis.

    Note:
        It turns out that the normal Gram-Schmidt algorithm suffers from
        numerical instability: Round-off errors can accumulate and destroy
        orthogonality of the resulting vectors. We introduce the modified
        Gram-Schmidt procedure to help remedy this issue.

    Args:
        basis (list[spmatrix]): basis to orthonormalize.

    Returns:
        list[spmatrix]: orthonormalized basis.

    References:
        Algorithm can be found in https://www.math.uci.edu/~ttrogdon/105A/html/Lecture23.html
    """
    dim = len(basis)
    orth_basis = []

    for j in range(dim):
        orth_basis.append(basis[j] / hs_norm(basis[j]))
        for k in range(j + 1, dim):
            basis[k] = basis[k] - hs_scalar_product(orth_basis[j], basis[k]) * orth_basis[j]
    return orth_basis

gram_schmidt_generator(basis)

Gram-Schmidt algorithm to orthonormalize a basis.

Note

It turns out that the normal Gram-Schmidt algorithm suffers from numerical instability: Round-off errors can accumulate and destroy orthogonality of the resulting vectors. We introduce the modified Gram-Schmidt procedure to help remedy this issue.

Parameters:

Name Type Description Default
basis list[spmatrix]

basis to orthonormalize.

 required

Yields:

Type Description
list[spmatrix] | list[NDArray]

NDArray or spmatrix: orthonormalized basis element.
References

Algorithm can be found in https://www.math.uci.edu/~ttrogdon/105A/html/Lecture23.html

Source code in qoptcraft/math/gram_schmidt.py 
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def gram_schmidt_generator(basis: list[spmatrix] | list[NDArray]) -> list[spmatrix] | list[NDArray]:
    """Gram-Schmidt algorithm to orthonormalize a basis.

    Note:
        It turns out that the normal Gram-Schmidt algorithm suffers from
        numerical instability: Round-off errors can accumulate and destroy
        orthogonality of the resulting vectors. We introduce the modified
        Gram-Schmidt procedure to help remedy this issue.

    Args:
        basis (list[spmatrix]): basis to orthonormalize.

    Yields:
        NDArray or spmatrix: orthonormalized basis element.

    References:
        Algorithm can be found in https://www.math.uci.edu/~ttrogdon/105A/html/Lecture23.html
    """
    dim = len(basis)
    orth_basis = []

    for j in range(dim):
        orth_basis.append(basis[j] / hs_norm(basis[j]))
        yield orth_basis[j]
        for k in range(j + 1, dim):
            basis[k] = basis[k] - hs_scalar_product(orth_basis[j], basis[k]) * orth_basis[j]