# SparseDiffTools.jl
[![Join the chat at https://julialang.zulipchat.com #sciml-bridged](https://img.shields.io/static/v1?label=Zulip&message=chat&color=9558b2&labelColor=389826)](https://julialang.zulipchat.com/#narrow/stream/279055-sciml-bridged)
[![Global Docs](https://img.shields.io/badge/docs-SciML-blue.svg)](https://docs.sciml.ai/SparseDiffTools/stable/)
[![codecov](https://codecov.io/gh/JuliaDiff/SparseDiffTools.jl/branch/master/graph/badge.svg)](https://codecov.io/gh/JuliaDiff/SparseDiffTools.jl)
[![Build Status](https://github.com/JuliaDiff/SparseDiffTools.jl/workflows/CI/badge.svg)](https://github.com/JuliaDiff/SparseDiffTools.jl/actions?query=workflow%3ACI)
[![buildkite](https://badge.buildkite.com/ea7df061e20328f60d3e0816d97d2d856166f2ea7030748cef.svg)](https://buildkite.com/julialang/sparsedifftools-dot-jl)
[![ColPrac: Contributor's Guide on Collaborative Practices for Community Packages](https://img.shields.io/badge/ColPrac-Contributor's%20Guide-blueviolet)](https://github.com/SciML/ColPrac)
[![SciML Code Style](https://img.shields.io/static/v1?label=code%20style&message=SciML&color=9558b2&labelColor=389826)](https://github.com/SciML/SciMLStyle)
This package is for exploiting sparsity in Jacobians and Hessians to accelerate
computations. Matrix-free Jacobian-vector product and Hessian-vector product
operators are provided that are compatible with AbstractMatrix-based libraries
like IterativeSolvers.jl for easy and efficient Newton-Krylov implementation. It is
possible to perform matrix coloring, and utilize coloring in Jacobian and Hessian
construction.
Optionally, automatic and numerical differentiation are utilized.
## Example
Suppose we had the function
```julia
fcalls = 0
function f(y,x) # in-place
global fcalls += 1
for i in 2:length(x)-1
y[i] = x[i-1] - 2x[i] + x[i+1]
end
y[1] = -2x[1] + x[2]
y[end] = x[end-1] - 2x[end]
nothing
end
function g(x) # out-of-place
global fcalls += 1
y = zero(x)
for i in 2:length(x)-1
y[i] = x[i-1] - 2x[i] + x[i+1]
end
y[1] = -2x[1] + x[2]
y[end] = x[end-1] - 2x[end]
y
end
```
For this function, we know that the sparsity pattern of the Jacobian is a
`Tridiagonal` matrix. However, if we didn't know the sparsity pattern for
the Jacobian, we could use the `Symbolics.jacobian_sparsity` function to automatically
detect the sparsity pattern. We declare that the function `f` outputs a
vector of length 30 and takes in a vector of length 30, and `jacobian_sparsity` returns
a `SparseMatrixCSC`:
```julia
using Symbolics
input = rand(30)
output = similar(input)
sparsity_pattern = Symbolics.jacobian_sparsity(f,output,input)
jac = Float64.(sparsity_pattern)
```
Now we call `matrix_colors` to get the colorvec vector for that matrix:
```julia
using SparseDiffTools
colors = matrix_colors(jac)
```
Since `maximum(colors)` is 3, this means that finite differencing can now
compute the Jacobian in just 4 `f`-evaluations. Generating the sparsity
pattern used 1 (pseudo) `f`-evaluation, so the total number of times that
`f` is called to compute the sparsity pattern plus the entire 30x30 Jacobian
is 5 times:
```julia
using FiniteDiff
FiniteDiff.finite_difference_jacobian!(jac, f, rand(30), colorvec=colors)
@show fcalls # 5
```
In addition, a faster forward-mode autodiff call can be utilized as well:
```julia
forwarddiff_color_jacobian!(jac, f, x, colorvec = colors)
```
If one only needs to compute products, one can use the operators. For example,
```julia
x = rand(30)
J = JacVec(f,x)
```
makes `J` into a matrix-free operator which calculates `J*v` products. For
example:
```julia
v = rand(30)
res = similar(v)
mul!(res,J,v) # Does 1 f evaluation
```
makes `res = J*v`. Additional operators for `HesVec` exists, including
`HesVecGrad` which allows one to utilize a gradient function. These operators
are compatible with iterative solver libraries like IterativeSolvers.jl, meaning
the following performs the Newton-Krylov update iteration:
```julia
using IterativeSolvers
gmres!(res,J,v)
```
## Documentation
### Matrix Coloring
This library extends the common `ArrayInterfaceCore.matrix_colors` function to allow
for coloring sparse matrices using graphical techniques.
Matrix coloring allows you to reduce the number of times finite differencing
requires an `f` call to `maximum(colors)+1`, or reduces automatic differentiation
to using `maximum(colors)` partials. Since normally these values are `length(x)`,
this can be significant savings.
The API for computing the colorvec vector is:
```julia
matrix_colors(A::AbstractMatrix,alg::SparseDiffToolsColoringAlgorithm = GreedyD1Color();
partition_by_rows::Bool = false)
```
The first argument is the abstract matrix which represents the sparsity pattern
of the Jacobian. The second argument is the optional choice of coloring algorithm.
It will default to a greedy distance 1 coloring, though if your special matrix
type has more information, like is a `Tridiagonal` or `BlockBandedMatrix`, the
colorvec vector will be analytically calculated instead. The keyword argument
`partition_by_rows` allows you to partition the Jacobian on the basis of rows instead
of columns and generate a corresponding coloring vector which can be used for
reverse-mode AD. Default value is false.
The result is a vector which assigns a colorvec to each column (or row) of the matrix.
### Colorvec-Assisted Differentiation
Colorvec-assisted differentiation for numerical differentiation is provided by
FiniteDiff.jl and for automatic differentiation is provided by
ForwardDiff.jl.
For FiniteDiff.jl, one simply has to use the provided `colorvec` keyword
argument. See
[the FiniteDiff Jacobian documentation](https://github.com/JuliaDiff/FiniteDiff.jl#jacobians)
for more details.
For forward-mode automatic differentiation, use of a colorvec vector is provided
by the following function:
```julia
forwarddiff_color_jacobian!(J::AbstractMatrix{<:Number},
f,
x::AbstractArray{<:Number};
dx = nothing,
colorvec = eachindex(x),
sparsity = nothing)
```
Notice that if a sparsity pattern is not supplied then the built Jacobian will
be the compressed Jacobian: `sparsity` must be a sparse matrix or a structured matrix
(`Tridiagonal`, `Banded`, etc. conforming to the ArrayInterfaceCore.jl specs) with the
appropriate sparsity pattern to allow for decompression.
This call will allocate the cache variables each time. To avoid allocating the
cache, construct the cache in advance:
```julia
ForwardColorJacCache(f,x,_chunksize = nothing;
dx = nothing,
colorvec=1:length(x),
sparsity = nothing)
```
and utilize the following signature:
```julia
forwarddiff_color_jacobian!(J::AbstractMatrix{<:Number},
f,
x::AbstractArray{<:Number},
jac_cache::ForwardColorJacCache)
```
`dx` is a pre-allocated output vector which is used to declare the output size,
and thus allows for specifying a non-square Jacobian.
If one is using an out-of-place function `f(x)`, then the alternative form
ca be used:
```julia
jacout = forwarddiff_color_jacobian(g, x,
dx = similar(x),
colorvec = 1:length(x),
sparsity = nothing,
jac_prototype = nothing)
```
Note that the out-of-place form is efficient and compatible with StaticArrays.
One can specify the type and shape of the output Jacobian by giving an
additional `jac_prototype` to the out-of place `forwarddiff_color_jacobian`
function, otherwise it will become a dense matrix. If `jac_prototype` and
`sparsity` are not specified, then the oop Jacobian will assume that the
function has a *square* Jacobian ma
没有合适的资源?快使用搜索试试~ 我知道了~
通过稀疏性利用和矩阵着色进行快速雅可比计算_.zip
共50个文件
jl:31个
yml:8个
toml:4个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 69 浏览量
2023-04-13
23:37:07
上传
评论
收藏 79KB ZIP 举报
温馨提示
通过稀疏性利用和矩阵着色进行快速雅可比计算_.zip
资源推荐
资源详情
资源评论
收起资源包目录
通过稀疏性利用和矩阵着色进行快速雅可比计算_.zip (50个子文件)
SparseDiffTools.jl-master
.github
dependabot.yml 255B
workflows
CompatHelper.yml 403B
Invalidations.yml 1KB
CI.yml 1KB
FormatCheck.yml 1KB
TagBot.yml 226B
Documentation.yml 866B
src
SparseDiffTools.jl 3KB
differentiation
compute_hessian_ad.jl 7KB
jaches_products.jl 11KB
vecjac_products.jl 3KB
compute_jacobian_ad.jl 18KB
coloring
matrix2graph.jl 2KB
greedy_star1_coloring.jl 2KB
acyclic_coloring.jl 7KB
backtracking_coloring.jl 6KB
high_level.jl 1KB
greedy_star2_coloring.jl 2KB
greedy_d1_coloring.jl 815B
contraction_coloring.jl 3KB
.buildkite
pipeline.yml 504B
LICENSE 1KB
docs
src
sparsedifftools.md 51B
assets
logo.png 26KB
favicon.ico 1KB
index.md 12KB
make.jl 509B
Project.toml 145B
pages.jl 113B
ext
SparseDiffToolsZygote.jl 3KB
test
test_gpu_ad.jl 1KB
runtests.jl 1KB
test_sparse_hessian.jl 5KB
test_contraction.jl 818B
test_integration.jl 1KB
test_ad.jl 8KB
test_vecjac_products.jl 2KB
test_greedy_star.jl 2KB
test_greedy_d1.jl 826B
update_coeffs_testutils.jl 515B
gpu
Project.toml 53B
test_jaches_products.jl 8KB
test_specialmatrices.jl 2KB
test_acyclic.jl 3KB
test_bsc.jl 2KB
test_matrix2graph.jl 1KB
.JuliaFormatter.toml 15B
.gitignore 68B
README.md 13KB
Project.toml 2KB
共 50 条
- 1
资源评论
快撑死的鱼
- 粉丝: 1w+
- 资源: 9154
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功