SparseMultiply
的 SparseMatrix_Double
和 DenseVector_Double
,使用 Accelerate 框架的 稀疏求解器,并且它随机崩溃:
有时,它会起作用。有时,它会因
EXC_BAD_ACCESS
而崩溃。有时,它会返回错误的结果。
我尝试在方案设置的“诊断”选项卡上打开各种“地址清理器”和/或各种内存检查选项,但它们没有报告任何问题。
发生什么事了?
func matrixProductExperiment() {
// Given sparse matrix A, and dense vector X, calculate product of dense vector Y, i.e., y = Ax:
//
// A X = Y
// ( 10.0 1.0 2.5 ) ( 2.20 ) = ( 32.025 )
// ( 1.0 12.0 -0.3 1.1 ) ( 2.85 ) = ( 38.720 )
// ( -0.3 9.5 ) ( 2.79 ) = ( 25.650 )
// ( 2.5 1.1 6.0 ) ( 2.87 ) = ( 25.855 )
// We use a format known as Compressed Sparse Column (CSC) to store the data. Further,
// as the matrix is symmetric, we only need to store half the data. The CSC format
// stores the matrix as a series of column vectors where only the non-zero entries are
// specified, stored as the pair of (row index, value), although in separate arrays:
let rowCount: Int32 = 4
let columnCount: Int32 = 4
var matrixValues = [ 10.0, 1.0, 2.5, 12.0, -0.3, 1.1, 9.5, 6.0 ]
var rowIndices: [Int32] = [ 0, 1, 3, 1, 2, 3, 2, 3 ]
var columnStarts = [ 0, 3, 6, 7 ]
// vector X
var xValues = [ 2.20, 2.85, 2.79, 2.87 ]
// In this library, this raw information is all wrapper into a flexible data type
// that allows for more complex use cases in other situations.
rowIndices.withUnsafeMutableBufferPointer { rowIndicesPointer in
columnStarts.withUnsafeMutableBufferPointer { columnStartsPointer in
matrixValues.withUnsafeMutableBufferPointer { valuesPointer in
xValues.withUnsafeMutableBufferPointer { xPointer in
let a = SparseMatrix_Double(
// Structure of the matrix, without any values
structure: SparseMatrixStructure(
rowCount: rowCount,
columnCount: columnCount,
columnStarts: columnStartsPointer.baseAddress!,
rowIndices: rowIndicesPointer.baseAddress!,
// Matrix meta-data
attributes: SparseAttributes_t(
transpose: false,
triangle: SparseLowerTriangle,
kind: SparseSymmetric,
_reserved: 0,
_allocatedBySparse: false
),
blockSize: 1),
// Numerical values of the matrix
data: valuesPointer.baseAddress!
)
let x = DenseVector_Double(count: columnCount, data: xPointer.baseAddress!)
let y = [Double](unsafeUninitializedCapacity: Int(rowCount)) { resultBuffer, count in
let y = DenseVector_Double(count: rowCount, data: resultBuffer.baseAddress!)
SparseMultiply(a, x, y)
count = Int(rowCount)
}
print(y) // [32.025, 38.72, 25.65, 25.855] – Correct
}
}
}
}
}
问题是
columnStarts
。在所有实际的“列开始”之后,该数组必须包含矩阵值数组中的元素数量(以便它可以计算最后一列中有多少元素)。请注意 columnStarts
数组末尾的额外值:
func matrixProductExperiment() {
…
let rowCount: Int32 = 4
let columnCount: Int32 = 4
var matrixValues = [ 10.0, 1.0, 2.5, 12.0, -0.3, 1.1, 9.5, 6.0 ]
var rowIndices: [Int32] = [ 0, 1, 3, 1, 2, 3, 2, 3 ]
var columnStarts = [ 0, 3, 6, 7, 8 ]
assert(columnStarts.last == matrixValues.count, "\(String(describing: columnStarts.last)) ≠ \(matrixValues.count)")
…
}
如果您使用
SparseConvertFromCoordinate
,如 SparseMultiply
文档中所示,则需要提供 blockCount
。但是 SparseMatrixStructure
初始化器没有“块计数”参数,并且它从 columnStarts
中的最后一个值中提取此参数(有点不明显,恕我直言)。
请参阅创建稀疏矩阵,其中显示:
此数组需要一个额外的最终条目来定义最终列的长度。
在我看来,“开始”数组必须以矩阵值的“计数”结束并不完全直观,但回想起来,我们可以明白为什么我们必须这样做。
那是我一生中再也回不来的几个小时。解决方案对许多人来说可能是显而易见的,但对于那些因 Accelerate 中的稀疏矩阵随机崩溃而陷入困境的人,请仔细查看
columnStarts
数组。该值不具有有意义的验证和/或错误消息。如果忽略计数,则会收到间歇性/神秘错误。
这对我来说是一个愚蠢的错误,但追查问题需要做很多工作。希望这将为一些未来的读者节省几个小时的时间。