1
2
3
4
5
6
7
8
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
35
36
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
// Copyright ©2021 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package gonum
import (
"math"
"gonum.org/v1/gonum/blas/blas64"
)
// Dgetc2 computes an LU factorization with complete pivoting of the n×n matrix
// A. The factorization has the form
//
// A = P * L * U * Q,
//
// where P and Q are permutation matrices, L is lower triangular with unit
// diagonal elements and U is upper triangular.
//
// On entry, a contains the matrix A to be factored. On return, a is overwritten
// with the factors L and U. The unit diagonal elements of L are not stored.
//
// On return, ipiv and jpiv contain the pivot indices: row i has been
// interchanged with row ipiv[i] and column j has been interchanged with column
// jpiv[j]. ipiv and jpiv must have length n, otherwise Dgetc2 will panic.
//
// If k is non-negative, then U[k,k] is likely to produce overflow when solving
// for x in A*x=b and U has been perturbed to avoid the overflow.
//
// Dgetc2 is an internal routine. It is exported for testing purposes.
func (impl Implementation) Dgetc2(n int, a []float64, lda int, ipiv, jpiv []int) (k int) {
switch {
case n < 0:
panic(nLT0)
case lda < max(1, n):
panic(badLdA)
}
// Negative k indicates U was not perturbed.
k = -1
// Quick return if possible.
if n == 0 {
return k
}
switch {
case len(a) < (n-1)*lda+n:
panic(shortA)
case len(ipiv) != n:
panic(badLenIpiv)
case len(jpiv) != n:
panic(badLenJpvt)
}
const (
eps = dlamchP
smlnum = dlamchS / eps
)
if n == 1 {
ipiv[0], jpiv[0] = 0, 0
if math.Abs(a[0]) < smlnum {
k = 0
a[0] = smlnum
}
return k
}
// Factorize A using complete pivoting.
// Set pivots less than smin to smin.
var smin float64
var ipv, jpv int
bi := blas64.Implementation()
for i := 0; i < n-1; i++ {
var xmax float64
for ip := i; ip < n; ip++ {
for jp := i; jp < n; jp++ {
if math.Abs(a[ip*lda+jp]) >= xmax {
xmax = math.Abs(a[ip*lda+jp])
ipv = ip
jpv = jp
}
}
}
if i == 0 {
smin = math.Max(eps*xmax, smlnum)
}
// Swap rows.
if ipv != i {
bi.Dswap(n, a[ipv*lda:], 1, a[i*lda:], 1)
}
ipiv[i] = ipv
// Swap columns.
if jpv != i {
bi.Dswap(n, a[jpv:], lda, a[i:], lda)
}
jpiv[i] = jpv
// Check for singularity.
if math.Abs(a[i*lda+i]) < smin {
k = i
a[i*lda+i] = smin
}
for j := i + 1; j < n; j++ {
a[j*lda+i] /= a[i*lda+i]
}
bi.Dger(n-i-1, n-i-1, -1, a[(i+1)*lda+i:], lda, a[i*lda+i+1:], 1, a[(i+1)*lda+i+1:], lda)
}
if math.Abs(a[(n-1)*lda+n-1]) < smin {
k = n - 1
a[(n-1)*lda+(n-1)] = smin
}
// Set last pivots to last index.
ipiv[n-1] = n - 1
jpiv[n-1] = n - 1
return k
}
|
