Comments (17)
Hi Field,
Think of an
from blis.
Seconding this, but I would suggest further generalizing from diagonal D
to symmetric/hermitian.
from blis.
@poulson @chriscoey Can you elaborate more on what you have in mind, since I'm unfamiliar with this operation?
Specifically, I'm interested in knowing the structure of A in C += alpha A (D A)^T
. (Also, what is an LDL factorization? It's not clear to me how this relates to your request, or if it is strictly unnecessary background / context.)
from blis.
from blis.
@rvdg Thanks, Robert. So is a real domain LDL factorization specified as A = L D L^T
?
from blis.
@fgvanzee yes. The updates in question are the A -= L D L^T updates for A11, A21, and A22 (depending on variant).
@poulson I implemented C = A D B multiplications (with D diagonal) in TBLIS (interface and implementation). C = A B D is also possible. It should be possible to port this to BLIS and also extend to ?syrk
.
@chriscoey we had an undergraduate working on general 3-matrix multiplication. @rvdg did that end up as a usable product?
from blis.
@fgvanzee Yes, Robert (@rvdg) already clarified. Such factorizations are especially useful for symmetric quasi-(semi)definite matrices, which are, up to permutation, of the form [A, B; B', -C]
, where A
, and C
are Hermitian positive-(semi)definite. In the definite case, one can show bounds (e.g., via Saunders' analysis) on the stability of such factorizations. In practice, Interior Point Methods are built on this type of factorization (with the semidefinite cases modified to be definite).
from blis.
I still haven't seen anyone relate C += alpha A (D A)^T
and A -= L D L^T
. Even after you nix the alpha, harmonize the +/-, and assume A (in the first expression) is unit lower triangular, those don't look like the same operation to me.
from blis.
Nevermind, I see now that they are equivalent.
EDIT: No, I take that back. I'm still in doubt.
from blis.
Let A = L
. I don't see how (D A)^T = D L^T
. The lhs applies the diagonal elements to the columns of A^T
(because (D A)^T = A^T D
) while the rhs applies the diagonal elements to the rows of L^T
.
This may seem like minutae, but I like to understand the operation before I think about implementing it.
Note: While I appreciate that there are sometimes rich stories to tell about the applications that employ these operations, I actually don't need to know how the operation is used (it just clutters my brain and doesn't stick anyway). I happily leave such knowledge-keeping to people like @poulson and @devinamatthews. :)
from blis.
@poulson I've never heard of a pivoted Cholesky factorization, but I get the idea!
from blis.
@fgvanzee The diagonal entries you divide by are sometimes called pivots even if you didn't permute. Per the other question: diagonally-pivoted Cholesky is useful for computing a rank-revealing factorization of a Hermitian positive semi-definite matrix.
from blis.
@poulson Ah, thanks for that clarification. I'd never encountered this alternate instance/usage of "pivot." Good to know. (The President might say I am a fake linear algebraist. Although I think he would struggle to even pronounce "algebraist" correctly.)
from blis.
The D of an LDL' factorization is actually NOT diagonal.
It is block-diagonal, with blocks of size 1x1 or 2x2.
An LDL factorization is like a Cholesky factorization, but for a matrix that is symmetric but not necessarily positive definite. L is unit lower triangular and D is diagonal.
from blis.
@pauldj Quasi-diagonal 'D" -- which I find useful to refer to as 'B', as in LBL -- is only needed for the general symmetric/Hermitian-indefinite case. It is provably not needed for symmetric quasi-definite matrices. Indeed, most Interior Point Methods have highly indefinite, highly ill-conditioned sparse systems that they factor with LDL with diagonal D.
from blis.
I have been looking for an open source implementation of this myself. Intel MKL has two routines to compute A * B * A^T, where A is a general matrix, and B is Hermitian (NOT necessarily positive definite). sypr
takes sparse A and B, whereas syprd
takes sparse A and dense B. They work very well -- but I have no clue what's going on under the hood.
from blis.
The original proposal to add an extension to ?syrk
to support C += alpha A (D A)^T
for general A and diagonal D was once discussed on the mailing list and even has an open PR #536.
I personally would be very interested to have this functionality available. One big use case is for Generalized Linear Models which are fit by an iterative solver. The hessian - required by 2nd order/Newton optimization methods - is given by
from blis.
Related Issues (20)
- Discussion for new level-1v/-1m-like operations HOT 23
- Multithreading.md does not introduce include file needed for function calls HOT 1
- make install doesn't work with new install directory HOT 2
- When could you support AMD Zen4 arch? HOT 7
- Discrepancy in Haswell Results for Dgemm HOT 5
- cspan: Suggesting an ergonomic C99 API with multidimensional matrices for BLIS HOT 10
- "Missing" symbols relative to OpenBLAS HOT 16
- triggers segfault in "make check" process with configuration --disable-sba-pools on CentOS (SkylakeX)
- Default BLIS_[MNK]T values never actually set HOT 9
- fatal error: malloc.h: No such file or directory HOT 2
- Header path for default source build and Debian should match HOT 6
- bli_gemmsup_rd_haswell_asm_d6x8m.c:1296:1:error:bp cannot be used in ams here HOT 2
- New release? HOT 6
- A more complete list of ARM cpu implementations
- arm64 cpu identification is not portable to BSDs HOT 2
- inconsistence between documentation and code for bli_?trmm3 HOT 5
- What is the best way to debug BLIS? HOT 2
- GPU support and PortBLAS HOT 4
- getting error as illegal instruction HOT 4
- Support compiler names with spaces HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from blis.